数据结构排序算法总结

数据结构排序算法总结

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

void print(int a[], int n ,int i){      cout<<i <<":";      for(int j= 0; j<8; j++){          cout<<a[j] <<" ";      }      cout<<endl;  }      void InsertSort(int a[], int n)  {      for(int i= 1; i<n; i++){          if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入              int j= i-1;               int x = a[i];        //复制为哨兵，即存储待排序元素              a[i] = a[i-1];           //先后移一个元素              while(x < a[j]){  //查找在有序表的插入位置                  a[j+1] = a[j];                  j--;         //元素后移              }              a[j+1] = x;      //插入到正确位置          }          print(a,n,i);           //打印每趟排序的结果      }        }    int main(){      int a[8] = {3,1,5,7,2,4,9,6};      InsertSort(a,8);      print(a,8,8);  }

时间复杂度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){     cout<<i <<":";     for(int j= 0; j<8; j++){         cout<<a[j] <<" ";     }     cout<<endl; } /** * 直接插入排序的一般形式 * * @param int dk 缩小增量，如果是直接插入排序，dk=1 * */    void ShellInsertSort(int a[], int n, int dk) {     for(int i= dk; i<n; ++i){         if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入             int j = i-dk;                int x = a[i];           //复制为哨兵，即存储待排序元素             a[i] = a[i-dk];         //首先后移一个元素             while(x < a[j]){     //查找在有序表的插入位置                 a[j+dk] = a[j];                 j -= dk;             //元素后移             }             a[j+dk] = x;            //插入到正确位置         }         print(a, n,i );     }        }    /** * 先按增量d（n/2,n为要排序数的个数进行希尔排序 * */ void shellSort(int a[], int n){        int dk = n/2;     while( dk >= 1  ){         ShellInsertSort(a, n, dk);         dk = dk/2;     } } int main(){     int a[8] = {3,1,5,7,2,4,9,6};     //ShellInsertSort(a,8,1); //直接插入排序     shellSort(a,8);           //希尔插入排序     print(a,8,8); }

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

3. 选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

算法实现：

void print(int a[], int n ,int i){      cout<<"第"<<i+1 <<"趟 : ";      for(int j= 0; j<8; j++){          cout<<a[j] <<"  ";      }      cout<<endl;  }  /**  * 数组的最小值  *  * @return int 数组的键值  */  int SelectMinKey(int a[], int n, int i)  {      int k = i;      for(int j=i+1 ;j< n; ++j) {          if(a[k] > a[j]) k = j;      }      return k;  }    /**  * 选择排序  *  */  void selectSort(int a[], int n){      int key, tmp;      for(int i = 0; i< n; ++i) {          key = SelectMinKey(a, n,i);           //选择最小的元素          if(key != i){              tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换          }          print(a,  n , i);      }  }  int main(){      int a[8] = {3,1,5,7,2,4,9,6};      cout<<"初始值：";      for(int j= 0; j<8; j++){          cout<<a[j] <<"  ";      }      cout<<endl<<endl;      selectSort(a, 8);      print(a,8,8);  }

简单选择排序的改进——二元选择排序

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

void SelectSort(int r[],int n) {      int i ,j , min ,max, tmp;      for (i=1 ;i <= n/2;i++) {            // 做不超过n/2趟选择排序           min = i; max = i ; //分别记录最大和最小关键字记录位置          for (j= i+1; j<= n-i; j++) {              if (r[j] > r[max]) {                   max = j ; continue ;               }                if (r[j]< r[min]) {                   min = j ;               }           }          //该交换操作还可分情况讨论以提高效率        tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;        tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;         }   }

4. 选择排序—堆排序（Heap Sort）

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

(b) 小顶堆序列：（12，36，24，85，47，30，53，91）

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。

再讨论对n 个元素初始建堆的过程。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

void print(int a[], int n){      for(int j= 0; j<n; j++){          cout<<a[j] <<"  ";      }      cout<<endl;  }        /**  * 已知H[s…m]除了H[s] 外均满足堆的定义  * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,   *  * @param H是待调整的堆数组  * @param s是待调整的数组元素的位置  * @param length是数组的长度  *  */  void HeapAdjust(int H[],int s, int length)  {      int tmp  = H[s];      int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)      while (child < length) {          if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)              ++child ;          }          if(H[s]<H[child]) {  // 如果较大的子结点大于父结点              H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点              s = child;       // 重新设置s ,即待调整的下一个结点的位置              child = 2*s+1;          }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出               break;          }          H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上      }      print(H,length);  }      /**  * 初始堆进行调整  * 将H[0..length-1]建成堆  * 调整完之后第一个元素是序列的最小的元素  */  void BuildingHeap(int H[], int length)  {       //最后一个有孩子的节点的位置 i=  (length -1) / 2      for (int i = (length -1) / 2 ; i >= 0; --i)          HeapAdjust(H,i,length);  }  /**  * 堆排序算法  */  void HeapSort(int H[],int length)  {      //初始堆      BuildingHeap(H, length);      //从最后一个元素开始对序列进行调整      for (int i = length - 1; i > 0; --i)      {          //交换堆顶元素H[0]和堆中最后一个元素          int temp = H[i]; H[i] = H[0]; H[0] = temp;          //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整          HeapAdjust(H,0,i);    }  }     int main(){      int H[10] = {3,1,5,7,2,4,9,6,10,8};      cout<<"初始值：";      print(H,10);      HeapSort(H,10);      //selectSort(a, 8);      cout<<"结果：";      print(H,10);    }

分析:

设树深度为k，从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

5. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

算法的实现：

void bubbleSort(int a[], int n){      for(int i =0 ; i< n-1; ++i) {          for(int j = 0; j < n-i-1; ++j) {              if(a[j] > a[j+1])              {                  int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;              }          }      }  }

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。

6. 交换排序—快速排序（Quick Sort）

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

算法的实现：

递归实现：

void print(int a[], int n){      for(int j= 0; j<n; j++){          cout<<a[j] <<"  ";      }      cout<<endl;  }    void swap(int *a, int *b)  {      int tmp = *a;      *a = *b;      *b = tmp;  }    int partition(int a[], int low, int high)  {      int privotKey = a[low];                             //基准元素      while(low < high){                                   //从表的两端交替地向中间扫描          while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端          swap(&a[low], &a[high]);          while(low < high  && a[low] <= privotKey ) ++low;          swap(&a[low], &a[high]);      }      print(a,10);      return low;  }      void quickSort(int a[], int low, int high){      if(low < high){          int privotLoc = partition(a,  low,  high);  //将表一分为二          quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序          quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序      }  }    int main(){      int a[10] = {3,1,5,7,2,4,9,6,10,8};      cout<<"初始值：";      print(a,10);      quickSort(a,0,9);      cout<<"结果：";      print(a,10);    }

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

7. 归并排序（Merge Sort）

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++；转⑵
否则，rf[k]=r[j]； j++； k++；转⑵//将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空合并结束。

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  {      int j,k;      for(j=m+1,k=i; i<=m && j <=n ; ++k){          if(r[j] < r[i]) rf[k] = r[j++];          else rf[k] = r[i++];      }      while(i <= m)  rf[k++] = r[i++];      while(j <= n)  rf[k++] = r[j++];  }

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

void print(int a[], int n){      for(int j= 0; j<n; j++){          cout<<a[j] <<"  ";      }      cout<<endl;  }    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  {      int j,k;      for(j=m+1,k=i; i<=m && j <=n ; ++k){          if(r[j] < r[i]) rf[k] = r[j++];          else rf[k] = r[i++];      }      while(i <= m)  rf[k++] = r[i++];      while(j <= n)  rf[k++] = r[j++];      print(rf,n+1);  }    void MergeSort(ElemType *r, ElemType *rf, int lenght)  {       int len = 1;      ElemType *q = r ;      ElemType *tmp ;      while(len < lenght) {          int s = len;          len = 2 * s ;          int i = 0;          while(i+ len <lenght){              Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并              i = i+ len;          }          if(i + s < lenght){              Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并          }          tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf      }  }      int main(){      int a[10] = {3,1,5,7,2,4,9,6,10,8};      int b[10];      MergeSort(a, b, 10);      print(b,10);      cout<<"结果：";      print(a,10);    }

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  {       ElemType *rf2;      if(s==t) r[s] = rf[s];      else      {           int m=(s+t)/2;          /*平分*p 表*/          MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/          MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/          Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/      }  }  void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  {   /*对顺序表*p 作归并排序*/      MSort(r, rf,0, n-1);  }

更多PHP相关知识，请访问PHP中文网！

更多相关文章

随机推荐