排序算法总结
稳定性
排序算法的稳定性是指同样大小的样本在排序之后不会改变原始的相对次序
排序总结
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 (SelectionSort) | O（N²） | O（1） | 无 |
| 冒泡排序 (BubbleSort) | O（N²） | O（1） | 有 |
| 插入排序 (InsertionSort) | O（N²） | O（1） | 有 |
| 归并排序 (MergeSort) | O（N * logN） | O（N） | 有 |
| 快速排序 (QuickSort) | O（N * logN） | O（logN） | 无 |
| 堆排序 (HeapSort) | O（N * logN） | O（1） | 无 |
| 计数排序 (CountSort) | O（N） | O（M） | 有 |
| 基数排序 (RadixSort) | O（N） | O（M） | 有 |
选择策略
（1）数据量非常小的情况下可以做到非常迅速：插入排序
（2）性能优异、实现简单且利于改进（面对不同业务可以选择不同划分策略）、不在乎稳定性：随机快排
（3）性能优异、不在乎额外空间占用、具有稳定性：归并排序
（4）性能优异、额外空间占用要求 O（1）、不在乎稳定性：堆排序