排序（四）排序优化
几种排序算法
| 时间复杂度 | 是否稳定 | 是否原地排序 | |
|---|---|---|---|
| 冒泡排序 | O(n²) | 稳定 | 是 |
| 插入排序 | O(n²) | 稳定 | 是 |
| 选择排序 | O(n²) | 不稳定 | 是 |
| 快速排序 | O(nlogn) | 不稳定 | 是 |
| 归并排序 | O(nlogn) | 稳定 | 不是 |
| 计数排序 | O(n+k),k是数据范围 | 稳定 | 不是 |
| 桶排序 | O(n) | 稳定 | 不是 |
| 基数排序 | O(dn),d是维度 | 稳定 | 不是 |
排序算法的选择
虽然线性排序时间复杂度比较低，但是适用场景特殊条件苛刻，所以不能选用线性排序作为通用排序算法。
对于小规模数据可以选择时间复杂度为O(n²)的算法，在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长；对于大规模的数据，可以选用时间复杂度为O(nlogn)的算法。为了兼顾任意规模的数据，会选择时间复杂度为O(nlogn)的算法，其中包括：归并排序、快速排序、堆排序等。
归并排序在平均、最坏时间复杂度上都为O(nlogn),但是归并排序不是原地排序，当需要排序的数据比较大时，就为占用额外过多内存，显然不合适。快速排序是原地排序，但最坏情况时间复杂度退化为O(n²)。
优化快速排序
分区点：选取分区点不够合理，导致数据全部分到一边，时间复杂度就会变为O(n²)，所以优化的关键在于分区点的选取。
- 三数取中法：取开头、结尾和中间数据，求平均值作为分区点
- 随机发：从概率学的角度，不太可能出现每次都选到最差分区点的情况
递归问题：快速排序是用递归实现的，递归过程中可能出现堆栈溢出。
- 限制递归深度
- 在堆上手动模拟一个函数调用栈，手动模拟递归入栈出栈，这样就没有栈大小限制（堆是内存中最大的一块）
