深入学习排序算法之稳定性、比较次数、交换次数探讨

怼烎@ 2022-05-28 11:57 217阅读 0赞

在学习排序算法时，出于效率考虑，经常容易看到算法的稳定性、比较次数及交换次数研究。特别是考试或者公司笔试题，经常出现这样的题目。由于排序算法有很多种，平时提出大家才能说出个大概，但真要考查这些细节，估计很多人都说不准确。博主下决心写此文章，彻底探查清楚这些问题，与大家共享之。

首先说明稳定性是指相同元素在排序后相对位置保持不变。个人感觉稳定性的含义在于更广泛情形下，排序元素通常具有多个键值，即可以按照多个标准来排序。稳定性则保证了按照一个键排序的结果可以为第二个键所用。举个例子，对于学生的课程成绩，通常会和学号、姓名列在一起，先按照学生学号排序，然后再根据成绩从高到低，这样，相同分数的学生则是按照学号排名。

其次是关于比较次数和交换次数，通常用于算法效率分析。基于比较的排序算法其性能最好是nlog(n)。因而，不同的优化都是向这个边界靠近。且不同的算法也有不同的应用场景，不完全是看复杂度。

下面逐个分析常见排序算法。

一、冒泡排序

冒泡排序的原理是将相邻元素比较，小的往左移动，大的往右，整个过程就像是水中气泡上浮。在相邻两个元素的比较中，如果相等，则没有必要交换。这一点，保证了冒泡排序的稳定性。无论相等的元素之前处于什么位置，在冒泡的效果下， 最终会相邻，只要相等元素不交换，就不会改变相对位置。所以冒泡排序是稳定的。

对于n个元素，相邻元素均要比较，共有(n-1)次。经过一回合冒泡过程后，最大元素沉淀到最右位置。第二回合， 只剩下(n-1)个元素，只需要比较(n-2)次。依次类推，其他比较次数为(n-3),......,2,1. 所以总共比较次数为n(n-1)/2，而且是固定为这个数目.

至于交换次数，这个取决于初始序列的逆序数。对于数组A\[1,...,n\]，如果对于i<j有A\[i\]>A\[j\]，则称(A\[i\],A\[j\])是一个逆序对，序列中逆序对的个数称为逆序数。

冒泡排序每次交换，只改变了相邻两元素的位置，不影响和其他元素之间的逆序关系，因而，逆序数只减1。所以，冒泡排序交换次数等于初始序列的逆序数。

二、选择排序

选择排序的原理是每回合找出最小元素，然后交换到前面位置。

选择排序是不稳定的排序算法，不稳定主要产生于交换。交换过程可能改变相同元素的相对位置，举个例子，序列（5，8，5，1），最小数是1，第一次交换，得到（1，8，5，5），元素5相对位置已经发生变化。

下面是比较次数。对于n个元素的序列，找出最小元素需要比较(n-1)次。第一回合后，序列只剩下(n-1)个元素，下一次找最小元素还需要(n-2)次比较。最后直到2个元素需要比较1次。所以最后比较次数总共为(n-1)+(n-2)+...+1=n(n-1)/2，且固定不变。

每一回合最多交换一次，有(n-1)回合，所以最多交换次数为(n-1）。

三、插入排序

插入排序基本原理是假定前面i个元素已经排好，接下来将第(i+1)个元素插入到前面的序列中，保证有序。循环插入所有元素，即完成排序。

插入第(i+1)元素如果是从后往前扫描，寻找比其小的元素，这叫作直接插入排序。如果是使用二分查找判断新元素位置，则叫作二分插入排序。两种插入排序都是稳定的。对于直接插入排序，新来元素位置是通过从后往前比较（寻找比其小或相等元素，假设是a\[j\]）来确定的，将新元素放在a\[j\]后即可，相等可以保证稳定性。对于二分插入排序，可以通过修改二分查找来保证稳定性，如下代码所示，但x\[mid\] == temp时，low指针右移，该操作可以保证相等元素不会被放到前面。

**\[cpp\]**  [view plain][]  [copy][view plain]

1. while (low <= high)     
2.    \{     
3.     mid = (low + high) / 2;     
4.     if (x\[mid\] <= temp)     
5.     \{     
6.      low = mid + 1;     
7.     \}     
8.     else    
9.     \{     
10.      high = mid - 1;     
11.     \}

直接插入排序每回合的比较次数和元素移动次数等于其原始位置和插入位置之间的偏移。最好情况下（有序），需要比较(n-1)次，移动0次；最差情况下，需要比较1+2+...+(n-1)=n(n-1)/2次，移动n(n-1)/2次。在程序实现上，通常会用一个临时变量(如temp）保存待插入元素，最后又将temp移动到相应位置上，因而在很多教材上第回合插入会多2次移动操作，本文在此指出这一点。从上面的分析可以发现，直接插入排序对于基本有序的初始序列，有较好效果，无论是比较次数还是移动次数，都很少。

二分插入排序仅仅是加快了查找这一过程，即减少了元素比较次数，对于m个有序的序列，二分查找最坏情况下比较次数为1+log(m)。因而，在插入排序中，元素比较次数为（n-1)+log(1\*2\*...\*(n-1)),在初始序列杂乱无章的情形下，其平均查找性能较好。

四、归并排序

归并的基本思想是合并多路有序数组，通常我们考虑两路归并算法。

归并排序是稳定的，这是因为，在进行多路归并时，如果各个序列当前元素均相等，可以令排在前面的子序列的元素先处理，不会打乱相等元素的顺序。

考虑元素比较次数，两个长度分别为m和n的有序数组，每次比较处理一个元素，因而合并的最多比较次数为(m+n-1)，最少比较次数为min(m,n)。对于两路归并，序列都是两两合并的。不妨假设元素个数为n=2^h，

第一次归并：合并两个长度为1的数组，总共有n/2个合并，比较次数为n/2。

第二次归并：合并两个长度为2的数组，最少比较次数是2，最多是3，总共有n/4次，比较次数是(2~3)n/4。

第三次归并：合并两个长度为4的数组，最少比较次数是4，最多是7，总共有n/8次合并，比较次数是(4-7)n/8。

第k次归并：合并两个长度为2^(k-1)的数组，最少比较次数是2^(k-1)，最多是2^k-1，总共合并n/(2^k)次，比较次数是\[2^(k-1)~(2^k-1)\](n/2^k)=n/2~n(1-1/2^k)。

按照这样的思路，可以估算比较次数下界为n/2\*h=nlog2(n)/2。上界为n\[h-(1/2+1/4+1/8+...+1/2^h)\]=n\[h-(1-1/2^h)\]=nlog2(n)-n+1。

综上所述，归并排序比较次数为nlog2(n)/2~nlog2(n)-n+1。

归并排序引入了一个与初始序列长度相同的数组来存储合并后的结果，因而不涉及交换。

五、快速排序

快速排序的基本思想是分治。

快排是不稳定的，关键在于划分过程。现有的几种划分过程，基本都是分两个指针从左右同时扫描，然后交换元素，交换过程很容易打乱元素位置。

元素比较次数，也就是其复杂性分析。理想情况下，快速排序每次划分都将原始序列划分为两个等长的子序列。所以其比较次数为T(n)=2T(n/2)+n，所以其平均期望时间为nlog(n)。但在最坏情况下，即序列有序情形下，每次划分只能分出一个元素，因而总共需要(n-1)次划分，总的比较次数为(n-1)+(n-2)+...+1=n(n-1)/2，即退化为O(n^2).

元素交换次数取决于序列，不知道怎么给出准确分析，只好略过。

六、堆排序

堆排序的基本思想是对序列建立最小堆，然后依次取堆顶元素、删除和调整堆。

堆排序是不稳定的，堆的删除操作直接将最后一个元素提到堆顶，然后再调整，该操作容易改变相同元素的顺序。

比较主要发生在堆调整过程中，堆排序可以分解为两个过程，一是建堆，二是移除元素。建堆过程中，自底而上，每个元素和其孩子结点比较，找最大元素，并调整。如果元素是从大到小排列的，即已经成堆的情形下，对于完全树，其比较次数为(n-1)。在不满足堆的前提下，还会发生递归调用，比较次数更多。调整过程中，把最后一个元素提到堆顶后，需要重新调整堆，此时还是需要比较和调整。因而，初始有序的序列，其比较次数不会有太大变化（此处有疑问，无法论证清楚）。所以，堆排序的比较次数较稳定的靠近nlog(n)。

堆调整过程中会发生交换，交换次数跟数据位置相关，目前没有见到有分析清楚这个的。

七、其他排序算法

除上述外，还有许多其他排序算法，如希尔排序、基数排序、桶排序等。

希尔排序将序列划分成多个子序列，先对子序列分别排序，然后减少子序列个数，重复该过程。在开始时，数据规模较小，到最后，数据多数有序，采用直接插入排序，整体来说，取得比较好的效果。

基数排序根据多个键值对序列进行分配，属于分配类算法。

最后，本文分析可以总结如下：

<table style="width:780px;color:rgb(69,69,69);font-size:16px;background-color:rgb(255,255,255);"> 
 <tbody> 
 <tr> 
 <td> </td> 
 <td>稳定性</td> 
 <td>比较次数</td> 
 <td>交换次数</td> 
 <td>空间复杂性</td> 
 <td>适用场景</td> 
 </tr> 
 <tr> 
 <td>冒泡排序</td> 
 <td>稳定</td> 
 <td>n(n-1)/2</td> 
 <td>逆序数</td> 
 <td>O(1)</td> 
 <td> </td> 
 </tr> 
 <tr> 
 <td>选择排序</td> 
 <td>不稳定</td> 
 <td>n(n-1)/2</td> 
 <td>0~(n-1)</td> 
 <td>O(1)</td> 
 <td> </td> 
 </tr> 
 <tr> 
 <td>插入排序</td> 
 <td>稳定</td> 
 <td>最好为(n-1)，最差为n(n-1)/2</td> 
 <td>最好为0，最差为n(n-1)/2</td> 
 <td>O(1)</td> 
 <td>初始序列大量有序</td> 
 </tr> 
 <tr> 
 <td>归并排序</td> 
 <td>稳定</td> 
 <td>nlog2(n)/2~nlog2(n)-n+1</td> 
 <td> </td> 
 <td>O(n)</td> 
 <td>大量数据排序，外排序</td> 
 </tr> 
 <tr> 
 <td>快速排序</td> 
 <td>不稳定</td> 
 <td>nlog(n)，最差为n(n-1)/2</td> 
 <td>无法分析</td> 
 <td>log(n)</td> 
 <td> </td> 
 </tr> 
 <tr> 
 <td>堆排序</td> 
 <td>不稳定</td> 
 <td>nlog(n)，和初始顺序关系不大</td> 
 <td>无法分析</td> 
 <td>O(1)</td> 
 <td> </td> 
 </tr> 
 </tbody> 
</table>

[view plain]: https://blog.csdn.net/dreamer2020/article/details/8740244#