面试笔试中遇到了好多次稳定排序，每次都跪在这儿。概念都懂，看来还是得背一背了。
- 插入排序
插入排序类似于打扑克牌时候的整牌过程，从左到右扫面数组，每次向左进行比较。好比每次摸到一张牌，然后将它整理进序列中。
这样，如果有两个相同的元素，排序之前在右边的元素与左边的元素在排序中进行比较时，就不会进行交换，依然停留在右边。故而插入排序是稳定的。 - 希尔排序
希尔排序是对插入排序的改进，为了使排在后面的小元素尽快到达序列前端。开始选择较大步长的序列进行插入排序，逐渐缩小步长。
在一次插入排序中，元素的相对顺序是不变的。但相同的元素可能处于不同的步长序列中，故而稳定性被破坏，是不稳定的。 - 冒泡排序
冒泡排序是对相邻元素进行比较，如果相等是不会进行交换的，故而是稳定的。 - 选择排序
选择排序中，每次都将正在扫描的元素与剩下序列中最小的元素交换。然而，这种交换可能使一个元素交换到与它相同元素的另一边。举个例子，4,9,4,1,5，第一个4和1交换后就会到第二个4的后面。
因此，选择排序是不稳定的。 - 归并排序
在归并排序中，可以在归并过程中设置：如果有相同元素，则把前面序列的元素保存在前面，这样就保证了稳定性。
因此，归并排序是稳定的。 快速排序
基数排序
基数排序是基于位进行排序，收集。相同元素会按顺序被收集，所以是稳定的，类似于排序车牌号。- 堆排序
当堆中Pop出最大/小的元素后，交换了堆末尾的元素到堆顶，然后再向下sink。有可能使原来两个相同元素中处于后面的那个因为交换而变到前面去。一个例子如下图
参考资料
- http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html