排序算法稳定性

稳定性：
用一句话总结排序算法的稳定性就是：同样的值，在排完序之后改不改变相对次序。
举例：arr[] = {3,2,1,2,1,3}，数组中共有1、2 、3各2个数，排完序之后arr1[] = {1,1,2,2,3,3}。稳定性是指排完序之后，arr[]中的第一个位置的1在arr1[]中是否还是第一个，arr[]中第2个位置的1在arr1[]中是否还在第二个。
如果能保持不变，证明这个算法有稳定性，否则，则称为没有稳定性。

这种有稳定性的排序对基础类型的数据来讲是没用的，1就是1、2就是2，相同数字之间任顺序调换，丝毫没有影响，但是如果是自定义的类就不同了。

举例：
比如说：Student类中有班级class和年龄age属性。
第一次先用age有小到大进行排序。排完序之后 年龄小 -> 年龄大。
在紧接着用班级进行由小到大排序，此时如果这个算法是有稳定性的，那么排完序的结果里，1班学生的内部年龄也一定是从小到大的。2班学生的内部年龄也一定是从小到大的。

再比如说。商品价格区间100 - 200，先按照价格进行排序。再根据好评度进行排序。如果算法是由稳定性的，那么得到的结果中，第一条数据就是最物美价廉的商品。

排序算法总结：
基于之前更新的所有帖子中所介绍的算法做一个总结。

	时间复杂度	额外空间复杂度	稳定性
选择排序	$O(N^2)$	$O(1)$	无
冒泡排序	$O(N^2)$	$O(1)$	有
插入排序	$O(N^2)$	$O(1)$	有
归并排序	$O(N\ast lo{g}^N)$	$O(N)$	有
随机快排	$O(N\ast lo{g}^N)$	$O(logN)$	无
堆排序	$O(N\ast lo{g}^N)$	$O(1)$	无
==	==	==	==
计数排序	$O(N)$	$O(M)$	有
基数排序	$O(N)$	$O(N)$	有

总结：
为了绝对速度选快排，稳定性选归并排序，占用空间少选堆排序。