大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 八大常用排序算法

八大常用排序算法(2)

关键词:排序算法常用算法  阅读(1796) 赞(55)

[摘要]本文主要描述了八大常用排序算法,图文并茂,非常详细,希望对大家学习算法有所帮助!

5. 交换排序—冒泡排序(Bubble Sort)

基本思想:

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

冒泡排序的示例:

 

算法的实现:

  1. void bubbleSort(int a[], int n){  
  2.     for(int i =0 ; i< n-1; ++i) {  
  3.         for(int j = 0; j < n-i-1; ++j) {  
  4.             if(a[j] > a[j+1])  
  5.             {  
  6.                 int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
  7.             }  
  8.         }  
  9.     }  
  10. }  


冒泡排序算法的改进

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

1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

  1. void Bubble_1 ( int r[], int n) {  
  2.     int i= n -1;  //初始时,最后位置保持不变  
  3.     while ( i> 0) {   
  4.         int pos= 0; //每趟开始时,无记录交换  
  5.         for (int j= 0; j< i; j++)  
  6.             if (r[j]> r[j+1]) {  
  7.                 pos= j; //记录交换的位置   
  8.                 int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
  9.             }   
  10.         i= pos; //为下一趟排序作准备  
  11.      }   
  12. }    

2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

  1. void Bubble_2 ( int r[], int n){  
  2.     int low = 0;   
  3.     int high= n -1; //设置变量的初始值  
  4.     int tmp,j;  
  5.     while (low < high) {  
  6.         for (j= low; j< high; ++j) //正向冒泡,找到最大者  
  7.             if (r[j]> r[j+1]) {  
  8.                 tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
  9.             }   
  10.         --high;                 //修改high值, 前移一位  
  11.         for ( j=high; j>low; --j) //反向冒泡,找到最小者  
  12.             if (r[j]<r[j-1]) {  
  13.                 tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;  
  14.             }  
  15.         ++low;                  //修改low值,后移一位  
  16.     }   
  17. }   

6. 交换排序—快速排序(Quick Sort)

基本思想:

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

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

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

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

快速排序的示例:

(a)一趟排序的过程:

(b)排序的全过程

算法的实现:

 递归实现:

  1. void print(int a[], int n){  
  2.     for(int j= 0; j<n; j++){  
  3.         cout<<a[j] <<"  ";  
  4.     }  
  5.     cout<<endl;  
  6. }  
  7.   
  8. void swap(int *a, int *b)  
  9. {  
  10.     int tmp = *a;  
  11.     *a = *b;  
  12.     *b = tmp;  
  13. }  
  14.   
  15. int partition(int a[], int low, int high)  
  16. {  
  17.     int privotKey = a[low];                             //基准元素  
  18.     while(low < high){                                   //从表的两端交替地向中间扫描  
  19.         while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
  20.         swap(&a[low], &a[high]);  
  21.         while(low < high  && a[low] <= privotKey ) ++low;  
  22.         swap(&a[low], &a[high]);  
  23.     }  
  24.     print(a,10);  
  25.     return low;  
  26. }  
  27.   
  28.   
  29. void quickSort(int a[], int low, int high){  
  30.     if(low < high){  
  31.         int privotLoc = partition(a,  low,  high);  //将表一分为二  
  32.         quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
  33.         quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
  34.     }  
  35. }  
  36.   
  37. int main(){  
  38.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  39.     cout<<"初始值:";  
  40.     print(a,10);  
  41.     quickSort(a,0,9);  
  42.     cout<<"结果:";  
  43.     print(a,10);  
  44.   
  45. }  


分析:

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

 
快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下:

  1. void print(int a[], int n){  
  2.     for(int j= 0; j<n; j++){  
  3.         cout<<a[j] <<"  ";  
  4.     }  
  5.     cout<<endl;  
  6. }  
  7.   
  8. void swap(int *a, int *b)  
  9. {  
  10.     int tmp = *a;  
  11.     *a = *b;  
  12.     *b = tmp;  
  13. }  
  14.   
  15. int partition(int a[], int low, int high)  
  16. {  
  17.     int privotKey = a[low];                 //基准元素  
  18.     while(low < high){                   //从表的两端交替地向中间扫描  
  19.         while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
  20.         swap(&a[low], &a[high]);  
  21.         while(low < high  && a[low] <= privotKey ) ++low;  
  22.         swap(&a[low], &a[high]);  
  23.     }  
  24.     print(a,10);  
  25.     return low;  
  26. }  
  27.   
  28.   
  29. void qsort_improve(int r[ ],int low,int high, int k){  
  30.     if( high -low > k ) { //长度大于k时递归, k为指定的数  
  31.         int pivot = partition(r, low, high); // 调用的Partition算法保持不变  
  32.         qsort_improve(r, low, pivot - 1,k);  
  33.         qsort_improve(r, pivot + 1, high,k);  
  34.     }   
  35. }   
  36. void quickSort(int r[], int n, int k){  
  37.     qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序  
  38.   
  39.     //再用插入排序对基本有序序列排序  
  40.     for(int i=1; i<=n;i ++){  
  41.         int tmp = r[i];   
  42.         int j=i-1;  
  43.         while(tmp < r[j]){  
  44.             r[j+1]=r[j]; j=j-1;   
  45.         }  
  46.         r[j+1] = tmp;  
  47.     }   
  48.   
  49. }   
  50.   
  51.   
  52.   
  53. int main(){  
  54.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  55.     cout<<"初始值:";  
  56.     print(a,10);  
  57.     quickSort(a,9,4);  
  58.     cout<<"结果:";  
  59.     print(a,10);  
  60.   
  61. }  


7. 归并排序(Merge Sort)


基本思想:

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

归并排序示例:

 


合并方法:

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

  1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
  2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
  3. //选取r[i]和r[j]较小的存入辅助数组rf
    如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
    否则,rf[k]=r[j]; j++; k++; 转⑵
  4. //将尚未处理完的子表中元素存入rf
    如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
    如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
  5. 合并结束。
  1. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
  2. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
  3. {  
  4.     int j,k;  
  5.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
  6.         if(r[j] < r[i]) rf[k] = r[j++];  
  7.         else rf[k] = r[i++];  
  8.     }  
  9.     while(i <= m)  rf[k++] = r[i++];  
  10.     while(j <= n)  rf[k++] = r[j++];  
  11. }  


归并的迭代算法


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

  1. void print(int a[], int n){  
  2.     for(int j= 0; j<n; j++){  
  3.         cout<<a[j] <<"  ";  
  4.     }  
  5.     cout<<endl;  
  6. }  
  7.   
  8. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
  9. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
  10. {  
  11.     int j,k;  
  12.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
  13.         if(r[j] < r[i]) rf[k] = r[j++];  
  14.         else rf[k] = r[i++];  
  15.     }  
  16.     while(i <= m)  rf[k++] = r[i++];  
  17.     while(j <= n)  rf[k++] = r[j++];  
  18.     print(rf,n+1);  
  19. }  
  20.   
  21. void MergeSort(ElemType *r, ElemType *rf, int lenght)  
  22. {   
  23.     int len = 1;  
  24.     ElemType *q = r ;  
  25.     ElemType *tmp ;  
  26.     while(len < lenght) {  
  27.         int s = len;  
  28.         len = 2 * s ;  
  29.         int i = 0;  
  30.         while(i+ len <lenght){  
  31.             Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
  32.             i = i+ len;  
  33.         }  
  34.         if(i + s < lenght){  
  35.             Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
  36.         }  
  37.         tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf  
  38.     }  
  39. }  
  40.   
  41.   
  42. int main(){  
  43.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
  44.     int b[10];  
  45.     MergeSort(a, b, 10);  
  46.     print(b,10);  
  47.     cout<<"结果:";  
  48.     print(a,10);  
  49.   
  50. }  

两路归并的递归算法

  1. void MSort(ElemType *r, ElemType *rf,int s, int t)  
  2. {   
  3.     ElemType *rf2;  
  4.     if(s==t) r[s] = rf[s];  
  5.     else  
  6.     {   
  7.         int m=(s+t)/2;          /*平分*p 表*/  
  8.         MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
  9.         MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
  10.         Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
  11.     }  
  12. }  
  13. void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
  14. {   /*对顺序表*p 作归并排序*/  
  15.     MSort(r, rf,0, n-1);  
  16. }  

8. 桶排序/基数排序(Radix Sort)

说基数排序之前,我们先说桶排序:

基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
         简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  


 例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

 首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

  然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

  最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

  假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

  对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

  从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

  当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

        前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

        1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

        2)其次待排序的元素都要在一定的范围内等等。

       桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。


分配排序的基本思想:说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

实例:

扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
花色: 梅花< 方块< 红心< 黑心  
面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序,得到如下序列:


即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果,我们讨论两种排序方法。
方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                               

其中k1 称为最主位关键码,kd 称为最次位关键码     。

 

两种多关键码排序方法:

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

最高位优先(Most Significant Digit first)法,简称MSD 法

1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法,简称LSD 法

1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。


基于LSD方法的链式基数排序的基本思想

“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

基数排序:

是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

算法实现:

  1. Void RadixSort(Node L[],length,maxradix)  
  2. {  
  3.    int m,n,k,lsp;  
  4.    k=1;m=1;  
  5.    int temp[10][length-1];  
  6.    Empty(temp); //清空临时空间  
  7.    while(k<maxradix) //遍历所有关键字  
  8.    {  
  9.      for(int i=0;i<length;i++) //分配过程  
  10.     {  
  11.        if(L[i]<m)  
  12.           Temp[0][n]=L[i];  
  13.        else  
  14.           Lsp=(L[i]/m)%10; //确定关键字  
  15.        Temp[lsp][n]=L[i];  
  16.        n++;  
  17.    }  
  18.    CollectElement(L,Temp); //收集  
  19.    n=0;  
  20.    m=m*10;  
  21.   k++;  
  22.  }  
  23. }  





总结

各种排序的稳定性,时间复杂度和空间复杂度总结:

 我们比较时间复杂度函数的情况:


                             时间复杂度函数O(n)的增长情况

所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。


时间复杂度来说:

(1)平方阶(O(n2))排序
各类简单排序:直接插入、直接选择和冒泡排序;
 (2)线性对数阶(O(nlog2n))排序
快速排序堆排序归并排序
 (3)O(n1+§))排序,§是介于0和1之间的常数。

       希尔排序
(4)线性阶(O(n))排序
基数排序,此外还有桶、箱排序。

说明:

当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至On);

而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为On2);

原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

 

稳定性:

排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
     稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

 

选择排序算法准则:

每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

选择排序算法的依据

影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

1.待排序的记录数目n的大小;

2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

3.关键字的结构及其分布情况;

4.对排序稳定性的要求。

设待排序元素的个数为n.

1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

   快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
       堆排序 :  如果内存空间允许且要求稳定性的,

       归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

3)当n较小,可采用直接插入或直接选择排序。

    直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

    直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

5)一般不使用或不直接使用传统的冒泡排序。

6)基数排序
它是一种稳定的排序算法,但有一定的局限性:
1、关键字可分解。

2
、记录的关键字位数较少,如果密集更好
3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

«上一页12下一页»


相关评论