排序算法

算法分析

算法稳定性

如果一种排序算法不会改变关键码值相同的记录的相对顺序，则称为稳定的（stable）

不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a[j].key>=a[j+1].key，则两个相等的记录就会交换位置。再如，快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。

稳定性意义

1.实际应用时：当允许关键码值重复的时候，具有相同关键码值的记录之间本身就有某种内在的顺序，有些应用要求在排序的时候不改变具有相同关键码值的初始顺序，此时，算法稳定性就很有意义。例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法将毫无意义）。

2.算法设计时：如果排序算法是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所利用。基数排序就是这样，先按低位排序，逐次按高位排序，那么，低位相同的数据元素其先后位置顺序即使在高位也相同时是不会改变的。

3.算法优化时：在实际应用中，复杂类型记录的移动可能会成为影响程序整个运行时间的重要因素。如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能相对会少一些，减少花销。

常见算法稳定性

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

基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

直接插入排序（Insert Sort）

直接插入排序，又叫简单插入排序，逐个处理待排序的记录，每条新记录与前面已排序的子序列进行比较，将它插入到子序列的正确位置。

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

1 template
     
       2 void inssort(E A[],int n){  //Insertion Sort 3     for(int i=1;i
      
       0)&&(A[j]
       
        11 void swap(E A[],int i,int j){12     E temp=A[i];13     A[i]=A[j];14     A[j]=temp;15 }
       
      
     

最好情况:元素已经递增有序，每趟只需与前面的最后一个对象比较1次，总的比较次数为n-1。

最坏情况:元素递减有序，第i趟时需比较并且移动前面i个对象。则总的比较次数KCN和移动次数RMN分别为

平均情况:对于第i条记录，数据的前i-1条记录有一半的关键码比第i条的关键码大，因为平均情况就是最差情况的一半，关键码比较次数和对象移动次数约为(n^2)/4。因此，直接插入排序的时间复杂度为O(n2)。

冒泡排序（Bubble Sort）

冒泡排序就是把小的元素往前调或者把大的元素往后调。（以从小到大为例）每一轮都是比较相邻两个关键码（第1轮1和2，第2轮2和3......），如果遇到低序号的关键码值比高序号的大，则进行二者交换，否则不进行操作。一旦遇到最小关键码值，这个过程将使它像个“气泡”被推到数组顶部。因此每一轮都会固定一个当前最小的值。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

1 template
     
      2 void bubsort(E A[],int n){3     for(int i=0;i
      
       i;j--){5             if(A[j]
      
     

冒泡排序的最佳、平均、最差情况的运行时间几乎是相同的，比较是不可避免的，交换次数与插入排序的交换次数相同。

选择排序（Selection Sort）

选择排序在第i轮“选择”第i小的记录，并把该记录与数组中的第i个位置上的元素进行交换。其独特之处在于交换操作的次数很少。选择排序是不稳定的，举个栗子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了。

1 template
     
       2 void selsort(E A[],int n){ 3     for(int i=0;i
      
       i;j--){ 6             if(A[lowindex]>A[j]) 7                 lowindex=j;} 8         swap(A,lowindex,i); 9     }10 }
      
     

选择排序的比较次数是固定的，总的KCN次数是 n(n-1)/2；

最佳情况下：RMN=0; 最差情况：每一趟都要移动，总的RMN=3(n-1)

直接插入排序、冒泡排序和选择排序三种方法在平均及最差情况下的时间代价都是O(N2)，关键的瓶颈在于只比较相邻元素，因此比较和移动只能一步步的进行（选择排序除外），交换相邻记录称为一次交换(exchange)，因此，有时这些排序称为交换排序(exchange sort)。

希尔排序 (Shell Sort)

希尔排序也叫做缩小增量排序(diminishing increment sort)。shell排序利用了插入排序的最佳时间代价特性，将待排序序列变成基本有序的，然后再利用插入排序来完成最后的排序工作。（基本思想是：对待排记录序列先作“宏观”调整，再作“微观”调整。）

具体的算法步骤是：在执行每一次循环时，将记录序列分成若干子序列，并使得子序列中的元素在整个数组中的间距相同（间距称之为增量），然后分别对每个子序列进行插入排序。排序结束之后，减小增量，进行新一轮的排序，直至增量为1，即常规的插入排序。

显然是不稳定的。（由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。）

1 template
     
       2 void shellinsert(E A[],int n,int dk){
   //每一趟插入排序 3     for(int i=incr;i
      
       =incr)&&(A[j]
       
         9 void shellsort(E A[],int n){10     for(int i=n/2;i>2;i/=2){   //每一个增量（每一轮）11         for(int j=0;j
       
      
     

对特定的待排序序列，可以准确地估算关键码的比较次数和对象移动次数。但要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

Knuth利用大量的实验统计资料得出，当 n 很大时，关键码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。

shell排序说明有时可以利用一个算法的特殊性能，尽管在一般情况下该算法可能会慢的让人难以忍受

归并排序(Mergesort)

首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次进行，直到合成整个区间。

可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

​

1 //归并排序的标准实现 2 template 
     
       3 void mergesort(Elem A[], Elem temp[], 4                int left, int right) { 5   int mid = (left+right)/2;            //找到中间界，递归处理左右两个部分 6   if (left == right) return;               //将数组分为间距为1的数组 7   mergesort
      
       (A, temp, left, mid);        //递归处理左边的部分 8   mergesort
       
        (A, temp, mid+1, right); 9   for (int i=left; i<=right; i++) // 使用辅助数组存储待处理的组10     temp[i] = A[i];11   int i1 = left; int i2 = mid + 1;12   for (int curr=left; curr<=right; curr++) {13     if (i1 == mid+1)      // 左边界检查14       A[curr] = temp[i2++];15     else if (i2 > right)  //右边界检查16       A[curr] = temp[i1++];17     else if (temp[i1]
        
         24 void mergesort(Elem A[], Elem temp[],25                int left, int right) {26   if ((right-left) <= THRESHOLD) {27     inssort
         
          (&A[left],right-left+1);28     return;29   }30   int i, j, k, mid = (left+right)/2;  31  if (left == right) return;  32  mergesort
          
           (A, temp, left, mid); 33 mergesort
           
            (A, temp, mid+1, right); 34 for (i=mid; i>=left; i--) temp[i] = A[i]; 35 for (j=1; j<=right-mid; j++) 36 temp[right-j+1] = A[j+mid]; 37 for (i=left,j=right,k=left; k<=right; k++) 38 if (temp[i] < temp[j]) A[k] = temp[i++]; 39 else A[k] = temp[j--];}
           
          
         
        
       
      
     

算法总的时间复杂度为O(nlogn),该时间代价不依赖于待排序数组的相对顺序，因此这是最佳、平均、最差时间。

归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。

非递归算法：

在内部排序中，通常采用的是2路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列，这个操作对顺序表而言，是轻而易举的。

 

1 void MergePass ( Element &L1,  Element &L2,  2              int step, int Length ) {
   //一趟归并排序 3     i =0; 4     while ( i+2* step <= Length-1 ){ 5          Merge ( L1,  L2,  i,  i+ step -1, i+2* step -1); 6          i += 2 * step; 7     } 8     if ( i+ stepLen <= Length -1 ) 9          Merge ( L1, L2,  i,  i+ stepLen -1, Length -1 );10     else for ( j=i; j <= Length -1; j++ )11          L2[j] = L1[j];12 } 13 ​14 void MergeSort ( Element &list, int Length ) {15     Element tempList[MaxSize];16     int step = 1;17     while ( step < Length ) {18          MergePass (list, tempList, step ); step*= 2;19          MergePass (tempList, list, step ); step*= 2;20     }21 }

 

快速排序(QuickSort)

在一趟快速排序中，找一个记录，以它的关键字作为“枢轴(pivot)”，凡关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。

 

举个栗子：

 

 

在调整过程中，设立了两个指针：low 和high，它们的初值分别为：s 和 t， 之后逐渐减小 high，增加 low，并保证R[high].key≥52 和 R[low].key≤52,否则进行记录的“交换”。

因此，在经过一次快排之后，序列变成{23, 49,14, 36,(52) 58,61, 97, 80, 75} ，此时pivot找到了自己的位置。

在算法导论里面，快速排序选择都是元素序列的最后一个元素，假设元素序列如下{3,9,5A,6,8,5B}，这种情况下，和上面的情况一下，稳不稳定还是看判断的时候是否出现等号，但是如果选择不是这样的，我们假设一种特殊状况：{3,9,5A,5B,6,8,5C}，算法的实现是选择中间的5B作为中点，则不论等号与否，都是不稳定的。实际上，算法导论的选择是非常有意义的，了解其算法过程的人可以看到，这样的选择极大的降低了交换元素的复杂度和移动元素的次数。算法导论中是加了等号的，即≤最后一个元素的值被移到了左边，因而快速排序是不稳定的。

1 template
     
       2 void qsort(E A[],int i,int j){   //第一次调用时的形式是qsort(array,0,n-1) 3     if(j<=i)return; 4     int pivotindex=findpivot(A,i,j); 5     swap(A,pivotindex,j); 6     int k=partition
      
       (A,i-1,j,A[j]); 7     swap(A,k,j); 8     qsort
       
        (A,i,k-1); 9     qsort
        
         (A,k+1,j);10 }11 template
         
          12 inline int findpivot(E A[],int i,int j){   //规定枢轴13   return (i+j)/2;14 }15 template
          
           16 inline int partition(E A[],int low,int high,E& pivot){ //每一轮进行划分17 while(low
           
            =pivot)19 --high;20 A[low]=A[high];21 while(A[low]<=pivot)22 ++low;23 A[high]=A[low];24 }25 R[low]=R[0];26 return low;27 }
           
          
         
        
       
      
     

 

如果每次划分对一个对象定位后，若左侧与右侧子序列的长度相同，则下一步是对两个长度减半的子序列进行排序，这是最理想的情况。可以证明，函数quicksort的平均计算时间也是o(nlogn)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。在最坏的情况，即待排序序列已经从小到大有序时，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过n-1趟才能把所有对象定位，而且第i 趟需要经过n-i次比较，总的比较次数将达到n平方/2。排序速度退化到简单排序的水平，比直接插入排序还慢。

对于 n较大的平均情况而言，快速排序是“快速”的，但是当n很小时，这种排序方法比其它简单排序方法还要慢。

若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度，有一种改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象，取其关键码居中者作为基准对象。

堆排序(Heap Sort)

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

堆排序是不稳定的：比如：3 27 36 27，如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。

 

template 
     
      void heapsort(Elem A[], int n) { // Heapsort  Elem mval;  maxheap
      
        H(A, n, n);  for (int i=0; i
      
     

堆排序的最佳、平均、最差时间代价是O(nlogn)，在平均情况下它比快速排序慢一个常数因子，但是堆排序更适合外排序，处理数据集太大而不适合在内存中排序的情况。堆排序建堆很快，因此如果希望找数组中第k大的元素，可以用o(n+klogn),如果k很小，它的速度就会比其他算法快很多。

基数排序(Radixsort)

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

在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：

1.待排序记录以指针相链，构成一个链表；

2.“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同；

3.“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;

4.对每个关键字位均重复2)和 3) 两步。

1 template 
     
        2 void RadixSort ( staticlinklist
      
        &list,  3          const int d,  const int radix ) { 4     int rear[radix],  front[radix], n=list.CurrentSize; 5     for ( int i = 1; i < n; i++ ) 6         list.Data[i].setLink(i+1); 7     list. Data[n].setLink(0);          //静态链表初始化 8     int current = 1;                       //链表扫描指针 9     for ( i = d-1; i >= 0; i-- ) {    //做 d 趟分配.收集10         for ( int j = 0; j < radix; j++ )  front[j] = 0; 11         while ( current != 0 ) {     //逐个对象分配   12             int k = list.Data[current].getKey(i);13             //取当前对象关键码的第 i 位 14             if ( front[k] == 0)     //原链表为空,对象链入15            front[k] = current;      16        else                            //原链表非空,链尾链入17            list. Data[rear[k]].setLink (current);18        rear[k] = current;      //修改链尾指针19        current = list. Data[current].getLink ( );   20         }21         j = 0;            //从0号队列开始收集       22         while ( front[j] == 0 ) j++;     //空队列跳过23         current = front[j];  24                 list. Data[0].setLink (current);25         int last = rear[j];       26         for ( k = j+1; k < radix; k++)  //逐个队列链接        27               if ( front[k] ) {          28                 list. Data[last].setLink(front[k]);        29                 last = rear[k];            }       30        list. Data[last].setLink(0);    }}​​
      
     

若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。每趟对n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O( d ( n+radix))。

若基数radix相同，对于对象个数较多而关键码位数较少的情况，使用链式基数排序较好

基数排序需要增加n+2radix个附加链接指针

总结

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

本文参考资料及学习资源：

1.排序算法总结(很多图是从里面搬过来的)

2.算法稳定性：

3.匈牙利 Sapientia 大学的 6 种排序算法舞蹈视频，非常有创意

4.数据结构可视化：

5.排序算法可视化