排序算法学习整理
汇总
排序算法 | 时间复杂度·平均 | 时间复杂度·最好 | 时间复杂度·最坏 | 空间复杂度 | 排序方式 | 稳定性 |
冒泡排序 | 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(nlogn) | O(n2) | 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) | Out Place | 稳定 |
基数排序 | O(n∗k) | O(n∗k) | O(n∗k) | O(n+k) | Out Place | 稳定 |
- 稳定性:相等的值不会改变它们的先后顺序,则是稳定的。
References:
Runoob (opens new window)
图解排序算法(二)之希尔排序 (opens new window)
Sorting Algorithms Animations (opens new window)
十大经典排序算法(动图演示) (opens new window)
https://github.com/MisterBooo/Article
https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
https://www.crio.do/blog/top-10-sorting-algorithms/