冒泡排序、快速排序、归并排序、计数排序、桶排序、基数排序。下图为十种
排序算法的分类:
2.十种排序算法所需时间
十种排序算法分别其时间的需求如下表所示,其中 n 为所给数据个数。
排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
插入排序
O(n^2) O(n^2) O(n) O(1)
稳定
希尔排序
O(n^1.5) O(n^2) O(n) O(1)
不稳定
选择排序
O(n^2) O(n^2) O(n^2) O(1)
不稳定
堆排序
O(nlogn) O(nlogn) O(nlogn) O(1)
不稳定
冒泡排序
O(n^2) O(n^2) O(n) O(1)
稳定
快速排序
O(nlogn) O(n^2) O(nlogn) O(nlogn)
不稳定
归并排序
O(nlogn) O(nlogn) O(nlogn) O(n)
稳定
计数排序
O(n+k) O(n+k) O(n+k) O(n+k)
稳定
桶排序
O(n+k) O(n^2) O(n) O(n+k)
稳定
基数排序
O(n*k) O(n*k) O(n*k) O(n+k)
稳定
稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面。
不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b