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

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

        其次是关于比较次数和交换次数，通常用于算法效率分析。基于比较的排序算法其性能最好是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指针右移，该操作可以保证相等元素不会被放到前面。