几种排序算法的总结_5

几种排序算法的总结

1. 基于比较的算法：选择冒泡插入归并快速排序以及堆排序，这类算法，只要规定好两个样本怎么比大小就可以直接复用，同时时间复杂度的极限是O(N*logN）；
2. 不进行比较的排序：桶排序（计数排序，基数排序）；同时，这种排序对样本数据有严格要求（如非负、数的范围小等），不易改写；
3. 具有稳定性的有冒泡、插入、归并排序以及计数和基数排序；
4. 其他排序（如选择，快排，堆排序，希尔排序等）不稳定；
5. 时间复杂度O(NlogN),额外空间复杂度低于O(N),且稳定的基于比较的算法是不存在的；
6. 如何选择使用哪种算法呢？为了绝对的速度使用快速排序，为了省空间选择堆排序，为了稳定选择归并排序。
7. 注意：（Arrays.sort()方法对于基础类型采用的是双轴快排，对于引用数据类型采用的是归并排序。因为稳定性对引用类型很重要）
8. 归并排序的额外空间复杂度可以变成O(1),采用”归并排序 内部缓存法“，但是变得不再稳定。（让你用内部缓存法的纯属脑子瓦特了，有病呢不是！因为已经不稳定了，直接用堆排序不香吗？）
9. ”原地归并排序“不要信，会让时间复杂度变成O（N²）。（如果是这样，直接用插入不香吗？？干嘛还要用归并？？）
10. 快速排序可以变的稳定！但是完全没必要（因为对样本数据要求太多！）