| 算法 | 时间复杂度 | 稳定 | 原地 |
|---|---|---|---|
| 冒泡 | O(n2) | Y | Y |
| 插入 | O(n2) | Y | Y |
| 选择 | O(n2) | N | Y |
| 归并 | O(nlogn) | Y | N |
| 快速 | O(nlogn) | N | Y |
| 桶 | O(n) | Y | N |
| 计数 | O(n+k) k是数据范围 | Y | N |
| 基数 | O(dn) d是维度 | Y | N |
优化快排
最坏情况下快排的时间复杂度是O(n2)，如果数据本来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法的时间复杂度就会退化为O(n2)。主要愿意是分区点选的不够合理。
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
- 三数取中法
从区间的首、尾、中间分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。如果要排序的数组比较大，可以使用五数取中、十数取中。 - 随机法
每次从要排序的区间中，随机选择一个元素作为分区点。不能保证每次分区点都选择的比较好，但是从概率的角度来看，也不大可能出现每次分区点都选的很差的情况，平均情况下，这样选的分区点是比较好的。
快排是用递归来实现的，递归要警惕堆栈溢出。避免递归过深而堆栈过小，导致堆栈溢出。
- 限制递归深度，一旦递归过深，超过了设定的阈值就停止递归。
- 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。(将递归调用改写为循环非递归方式)
时间复杂度代表的是一个增长趋势。大O复杂度表示法中，会省略低阶、系数、常数。在小规模数据面前，O(n2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。
排序函数
Java
基础数据类型：
Arrays.sort() -> DualPivotQuicksort.sort()
- 元素个数<47，插入排序
- 元素个数47-286，快速排序
- 元素个数>286，归并排序（类似TimSort）
对象类型：
Collections.sort() -> Arrays.sort() -> TimSort
元素个数<32，采用二分查找插入排序Binary Sort；
元素个数>=32，采用归并排序，归并的核心是分区Run;
找连续升或者降的序列作为分区，分区最终被调整为升序后压入栈；
如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阈值minrun；
每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并；
最终栈内分区被全部合并，得到一个排序好的数组。
TimSort合并：
找出左分区最后一个元素在右分区的位置；
找出右分区第一个元素在左分区的位置；
仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的。