排序算法学习整理

汇总

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