排序算法
排序的定义
对一序列对象根据某个关键字进行排序。
排序分类
![sort_images](/steven-blogs/assets/sort_category-0c06cd5a.jpg)
术语说明
- 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
- 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。
- 内排序:所有排序操作都在内存中完成。
- 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。
- 时间复杂度:一个算法执行所耗费的时间。
- 空间复杂度:运行完一个程序所需内存的大小。
算法总结
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|
冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 稳定 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | In-place | 不稳定 |
插入排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 稳定 |
希尔排序 | O(nlogn) | O(nlog2n) | O(nlog2n) | O(1) | In-place | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Out-place | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | In-place | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | In-place | 不稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | Out-place | 稳定 |
桶排序 | O(n+k) | O(n+k) | O(n2) | O(n+k) | Out-place | 稳定 |
基数排序 | O(n×k) | O(n×k) | O(n×k) | O(n+k) | Out-place | 稳定 |
n: 数据规模; k: “桶”的个数; In-place: 占用常数内存,不占用额外内存;Out-place: 占用额外内存。