# 排序算法学习整理

# 汇总

排序算法 时间复杂度·平均 时间复杂度·最好 时间复杂度·最坏 空间复杂度 排序方式 稳定性
冒泡排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) In Place 稳定
选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) In Place 不稳定
插入排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) In Place 稳定
希尔排序 O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(n2)O(n^2 ) O(1)O(1) In Place 不稳定
归并排序 O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(n)O(n) Out Place 稳定
快速排序 O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(n2)O(n^2) O(logn)O(log_{}{n} ) In Place 不稳定
堆排序 O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(nlogn)O(n \log_{}{n} ) O(1)O(1) In Place 不稳定
计数排序 O(n+k)O(n + k) O(n+k)O(n + k) O(n+k)O(n + k) O(k)O(k) Out Place 稳定
桶排序 O(n+k)O(n + k) O(n+k)O(n + k) O(n2)O(n^2) O(n)O(n) Out Place 稳定
基数排序 O(nk)O(n * k) O(nk)O(n * k) O(nk)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/

上次更新: 2023/8/18 23:39:36