稳定性、比较次数 与 交换次数

https://blog.csdn.net/dreamer2020/article/details/8740244

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

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

一、冒泡排序

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

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

至于交换次数，这个取决于初始序列的逆序数。对于数组A[1,…,n]，如果对于iA[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指针右移，该操作可以保证相等元素不会被放到前面。

while (l <= r){
    mid = (l + r) >> 1;
    if (x[mid] <= mid) l = mid + 1;
    else r = mid - 1;
}

直接插入排序每回合的比较次数和元素移动次数等于其原始位置和插入位置之间的偏移。最好情况下（有序），需要比较(n-1)次，移动0次；最差情况下，需要比较1+2+…+(n-1)=n(n-1)/2次，移动n(n-1)/2次。

在程序实现上，通常会用一个临时变量(如temp）保存待插入元素，最后又将temp移动到相应位置上。从上面的分析可以发现，直接插入排序对于基本有序的初始序列，有较好效果，无论是比较次数还是移动次数，都很少。

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

](https://blog.csdn.net/dreamer2020/article/details/8740244)

四、归并排序

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

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

考虑元素比较次数，两个长度分别为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~n(1-1/2^k)。

按照这样的思路，可以估算比较次数
下界为n/2 h = n/2 log2(n) = 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)。