执行效率:
空间复杂度:原地排序(Sorted in place)。原地排序算法,就是特指空间复杂度是 O(1)
的排序算法。
有序度:
a[i] <= a[j]
,如果 i < j
的数量n
的数组 满序度 = n * (n - 1) / 2
满序度 = 6 * (6 - 1) / 2 = 15
稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
a
原本在 b
前面,而 a = b
,排序之后 a
仍然在 b
的前面a
原本在 b
的前面,而 a = b
,排序之后 a
可能会出现在 b
的后面名词解释:
n
:数据规模k
:桶的个数排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 原地排序 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | ✔ | ✔ |
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | ✔ | ✘ |
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | ✔ | ✔ |
希尔排序 | O(n log n) | O(n(log2/2n)) | O(n(log2/2n)) | O(1) | ✔ | ✘ |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✘ | ✔ |
快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log n) | ✔ | ✘ |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✘ | ✘ |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | ✘ | ✔ |
桶排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | ✘ | ✔ |
基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | ✘ | ✔ |
从分类上来讲:
带(*)的排序算法需要额外的空间。
nlogn 比 n^2 快多少?
n^2 | nlogn | faster | |
---|---|---|---|
n = 10 | 100 | 33 | 3 |
n = 100 | 10000 | 664 | 15 |
n = 1000 | 10^6 | 9966 | 100 |
n = 10000 | 10^8 | 132877 | 753 |
n = 100000 | 10^10 | 1660964 | 6020 |