转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720094279641210/
有关各种排序问题的稳定性，时间复杂度，比较次数大概是最经常问到的问题了。另外对于某些公司，对于大数据量的排序问题也会涉及，这样就可能牵扯到外排序。所以这里一并将外排序一般归并过程中所使用的败者树和胜者树，以及置换选择排序大概的描述一下。
常见的排序算法有这么几个：冒泡排序，快速排序，堆排序，归并排序，插入排序(直接插入，二分插入)，希尔排序，选择排序，计数排序，基数排序
稳定性定义及相关分析
首先讨论排序算法的稳定性，看稳定性是如何定义的：稳定性指对于key相等的两个元素，当排序后完成后它们依然可以保持原来的相对位置，比如A在B前，如果是稳定的，排序后A也应该在B之前，之所以定义这个稳定性，是因为A B这样的数据可能不止包含用来作为排序关键字的key，可能还有其他数据，所以这样AB的两个顺序是有区别的。同时我们可以看到一些算法实现中需要一个稳定性的排序为基础，比如基数排序需要一个稳定的排序解决某个基数上的排序。
需要说明一下：这个稳定是从算法层面上说的，即一个排序算法是稳定的，指“存在”一个实现使排序结果稳定，反之为不稳定。当然稳定的算法可能有不稳定的实现。
在分析稳定性时，提供一个判断稳定性的比较准确的法则：判断一个排序算法是否稳定的，最重要的在看排序过程中是否对非相邻的元素进行了比较交换。考虑一个可能引起不稳定的场景：比如在快速排序中，很明显快速排序的划分过程涉及到了不相邻元素的交换，这样很明显的看到在算法的某次执行的一个快照中，整个序列会出现一种稳定性被破坏的状态。比如 5 5 1 6 3,假设以3进行划分，当扫描到1的时候，5需要与1交换，这样变成了1 5 5 6 3，很明显5的相对顺序发生了变化，而算法根本无法认识到这个变化。 也就根本无法从这个变化中恢复被破坏的稳定性。
从这一点也可以看到另一个更深层次的特点，算法执行的某刻有稳定性被破坏的状态，同时无法被意识到。实际上可以证明，如果在排序过程的某个时刻中，出现了一个不稳定的情况，那这个算法肯定就是一个不稳定的排序算法。
为什么呢？我们来看，如果某个时刻出现了一个key相等元素顺序的颠倒，那我们可以说明它肯定是不稳定的。因为如果它是稳定的，那么意味着最后排完序后，这个元素还需要被颠倒回去。但是如果我们将现在的这个中间过程中的元素顺序，重新作为一个新的输入，那麽如果按照原来的执行流程，是不是在最终的结果中这个元素又会被颠倒，虽然它们与原始序列相比是稳定的，但与这个新的序列相比就不是稳定的了。所以不管怎样，因为它们是互斥的，必然有其中一个会是不稳定的。
可能这个说明并非严格正确，但从某种程度上支持了上述的那些不稳定的症状。但是我们最好是能在每次迭代完成后找到这个不稳定状态，这样可能使程序整个运行的状态将是上次那个初始输入的一个子状态。也就是说如果我们从中间拿出一个状态，以这个状态作为初始状态执行，程序仍按照上次的执行序列执行下去就可以说明上述的那个证明了。所以严格来说，应该是在每次一个初始迭代，即需要程序的其他状态，比如寄存器，其他变量的值与那个中间状态保持一致，这样才能保证与上次输入获得一个相同的执行序列。比如针对上面的快速排序来说，我们希望可以说明在某次划分完成之后，会出现这种状态。而不是上面的那个划分中的中间状态，实际上是可以找到的，因为如果这次划分的最后我们还要把3放到放到里面的位置，这样我们就会使这个3可能落在一个不稳定的位置，因为序列中可能存在其他的3，使得它与这些3顺序颠倒了。这样我们就在一个划分结束后，找到了一个不稳定的情况。
排序算法实例分析
下面按排序算法逐个讨论：
冒泡排序
冒泡是一个形象的说法。它通过比较相邻的元素，可以把大的元素沉下去，或者反向来做把最小的元素浮上来。每次只是对相邻元素进行了比较，这样我们可以在key相等的时候，不做交换，这样很明显的可以保证执行中的每个时刻元素的排列都是稳定的。算法复杂度是O(n^2),不需要额外空间。
快速排序
快速排序主要利用了划分的思想。这个算法是不稳定的，看前面的分析可知。算法平均复杂度为O(nlogn),最坏可以退化为O(n^2)，不需要额外空间。如果考虑递归的空间，则空间花费与递归深度相关。
堆排序
这个也是不稳定的，堆排序主要利用了堆这个数据结构。通过不断的将堆中的最小数据删除排好序，堆中的extract-min操作，需要通过heapify-down操作，这个操作会使元素与左右孩子交换，显然这也涉及到了不相邻元素的交换，同样在这个过程中会出现不稳定的情况。时间复杂度为O(nlogn)。
归并排序
这个也是稳定的，虽然它不只涉及了相邻元素的比较，但是我们可以保证在归并的过程中使key相等的元素的相对位置保持不变。归并的时间复杂度为O(nlogn)，如果不使用原地归并，需要一个O(n)的额外空间。
插入排序(直接插入，二分插入)
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
选择排序
直接选择排序：直接选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
那是不是稳定的呢，我们可以观察一次扫描中，要交换最小的一个与第一个数据，最小的这个我们可以保证它依然稳定，但我们能否保证第一个数据依然不破坏稳定呢？答案是不可以，比如 2 3 2" 1，2与1交换后1 3 2" 2，这样的确就不是稳定的了。根据我们上面的分析，我们把1 3 2" 2作为一个新的序列我们可以发现，它应当与上面的2" 3 2 1执行到1 3 2" 2处的执行序列一样，严格说明了它肯定不稳定。因为要麽使2 3 2" 1不稳定，要麽使1 3 2" 2不稳定。
实际上如果用链表实现一个直接选择排序，这样它只改变了最小元素的位置，并没有交换，这样可以是稳定的，但一般的直接选择排序是指上面用交换的方法。
希尔排序
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
计数排序
稳定的，时间复杂度为O(n),参见clrs。
基数排序
稳定的。时间接近于线性。
综上，不稳定的有：快速排序 堆排序 选择排序 希尔排序。稳定的则是：冒泡排序 归并排序 插入排序 计数排序 基数排序
外排序
外排序的出现是由于内存不够大，待排序的数据又太多无法一次放入内存。因此很自然的想法，就是分多次放入内存。外排序就是使用这样的思路，首先把数据分成可以放入内存的一些块，将这些块搬入内存排好序，然后再输出形成一系列初始归并段，之后就是将这些有序的段，进行归并。所以首先是排序，然后是归并，只不过针对这两个过程，可能产生一些不同的方法。
比如对于初始归并段的排序，常见的我们可以直接把数据划分为相同大小的数据段，然后分别搬入内存进行排序。
但是也可以采用特殊些的方法，比如置换选择排序，就是用来形成初始归并段的，主要由于它平均情况下可以利用n个空间，产生2n个有序的数，所以很适合使用在这里。置换选择排序，使用了一个堆，如果从小到大排序，则使用一个最小堆，首先得到m个元素，建立最小堆，然后输出最小值，同时得到下一个输入，如果后面来的数，比已排序的最大值大就把它放到堆里，然后输出堆里的最小值，如果比当前的值小，就直接输出堆里的最小值，并把堆大小减1，把它放到堆中空出来的位置上。当堆减少为1时，重新建堆，并开始上面的过程。这样保证了输出的序列是不断递增的。可见，它对排列以及有序的序列十分高效，一次扫描就可以排好序了。
归并的方法有二路归并，三路…k路归并。归并的时候可以借助胜者树，或者败者树来选择最小值，如果归并段的长度不同还会涉及到最优归并。最优归并实际上等价于一个k叉huffman树，当k>2时，比如一个三路归并，如果只有4个初始段，那么实际上还需要增加一个虚段。才能保证每次归并都有三路，同时这个虚段要作为一个长度为0的子段参与huffman算法中。
同时对于败者树来说，它更新时只需要与它的直接父亲比较，而且有时候它的父亲不用改变。而胜者树则不然，它不仅需要与兄弟比较，而且因为当前删除的就是那个胜者，所以所有的父亲都必然需要更新，所以涉及到了更多节点的读写，效率会低。
对于败者树，节点实际是两个子树的最优秀的那个失败者，而不是这个树中最失败的，只是两个子树最优秀中的失败者，这点需要注意理解。同时一个败者树可以从胜者树构建而来。