排序算法总结

 常见排序算法的时间复杂度、空间复杂度及稳定性分析：

		时间复杂度	空间复杂度	是否有稳定性
基于比较的排序算法	选择排序	O(N^2)	O(1)	否
	冒泡排序	O(N^2)	O(1)	是
	插入排序	O(N^2)	O(1)	是
	归并排序	O(N*logN)	O(N)，每次需要额外一个数组用于拷贝	是
	快排	O(N*logN)	O(logN)	否
	堆排序	O(N*logN)	O(1)，数组本身可以作为堆，用的只是有限几个变量	否，堆插入的过程不稳定如果最后插入一个
不基于比较的排序算法	计数排序	O(N)	O(M),M表示数的枚举值个数	是
	基数排序	O(N)	O(N)	是

（1）不基于比较的排序，对样本数据有严格的要求，不易改写

（2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用。

（3）基于比较的排序，时间复杂度的极限是O(N*logN)

（4）时间复杂度为O(N*logN),额外空间复杂度低于O(N)且稳定的基于比较的排序是不存在的。

（5）为了绝对速度选快排，为了省空间选堆排，为了稳定性选归并

稳定性分析：

选择排序：肯定做不到稳定性，比如原来的数组是[5,5,5,5,5,3,5,5]，每次选最小的与0位置做交换，那原来0位置的5会越过1,2,3,4位置的5来到5位置。

冒泡排序：取决于相等的时候怎么处理相等，如果相等不交换就能保证稳定（如果相等还要交换的话也就不会有稳定性了）

插入排序：和冒泡排序一样，取决于怎么处理相等。

归并排序：也是处理相等的时候，相等的时候先拷贝左边的就可以保证稳定性（先拷贝右边不行，因为左组的元素在原来数组中是在右组的元素之前的）。

快速排序：无法保证稳定性，因为Partition过程做不到稳定，比如原数组是[4,4,4,4,1,4,3],我们以快排1.0为例，先选数组最后一个数字去做划分值，当遍历到4为止的1的时候，1比3小，需要和0位置的4做交换，0位置的4换到了4位置，跨过了1,2,3位置的4，其他快排也是类似的

堆排序：完全保证不了稳定性，整体调成大根堆或者小根堆的过程就不稳定，比如数组是[4,4,4,4,4,4,4,4,6]，前7个4插入结束后，堆是这样的：

 当最后一个6来了之后需要先跟3交换，然后和1交换，然后和0交换

 原数组中1位置的4跑到了2位置之后，3位置的4跑到了4，5，6之后

三种O(N * logN)的比较排序，如果追求速度用快排，因为

单纯追求速度使用快排：虽然时间复杂度是一样的，但是快排的常数时间更好

追求稳定性用归并：三个算法中唯一的稳定性算法

追求绝对的省空间适用堆排序：数组本身可以作为堆，用的只是有限几个变量

目前来说时间复杂度为O(N*logN),额外空间复杂度低于O(N)且稳定的基于比较的排序是不存在的。

Java自带的Arrays.sort的排序逻辑：

如果是基础类型，使用改进后的快排，因为基础类型排序，稳定性不重要而快排确实是最快的，时间常数最好的

如果是引用类型使用归并排序，也许稳定性不一定需要，但是未知的东西我们不能认为没有，只能考虑最差情况，为了保证稳定性，O(N*logN)只能用归并，且要保证相等时拷贝左边半区的元素

部分语言中会在快排的算法中写类似L + 60 < R使用插入排序的逻辑，这是因为虽然插入排序的时间复杂度是O(N^2),但是它的常数项更好，在数据量比较小的情况下插入排序执行时间可能小于快速排序，60是在长期实验条件下确定的值，这是工程上对于排序算法的改进。