排序算法稳定性：如果Ai= Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。
好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。
（如，一个班的学生已经按照学号大小排好序了，我现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。你选择的年龄排序方法如果是不稳定的，是不是排序完了后年龄相同的一组学生学号就乱了，你就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法，我就只需要按照年龄排一遍就好了。）
各排序算法比较
一、冒泡排序
略
二、选择排序
原理：初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的列头。以此类推，直到所有元素均排序完毕。（有点像冒泡，只是不换顺序而是记录最小值放列头）
选择排序
选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。
三、直接插入排序
直接插入
插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。
四、插入排序的高效改进：希尔排序
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。
原理：“采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行O(N^2)的交换次数，这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了“
希尔排序
转自知乎，图侵删
步长的选择
步长
五、归并排序
归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
归并排序除了可以对数组进行排序，还可以高效的求出数组小和（即单调和）以及数组中的逆序对
归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
1、设定两个指针，最初位置分别为两个已经排序序列的起始位置
2、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
3、重复步骤3直到某一指针到达序列尾
4、将另一序列剩下的所有元素直接复制到合并序列尾
递归实现原理
递归实现：
递归实现
非递归实现，即一开始以连个相邻元素处理归并（非递归比递归快）
一开始按单个处理
非递归实现
六、堆排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次大值。如此反复执行，便能得到一个有序序列了
堆排序
文字说明转自 https://www.cnblogs.com/chengxiao/p/6129630.html
七、快速排序
原理：
1、先从数列中取出一个数作为基准数
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3、再对左右区间重复第二步，直到各区间只有一个数
“快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。”
快速排序
快速排序
文字说明转自http://developer.51cto.com/art/201403/430986.htm
1、基准值的取值不一定取最左值，可以取最左最左最右中间值中的最小值等等
2、对于基础类型，底层使用快速排序。对于非基础类型，底层使用归并排序。这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它是不稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。
网友评论