目录
内部排序算法的比较
| 算法种类 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 | 排序趟数与序列初态有无关系 | 比较次数与序列初态有无关系 |
|---|---|---|---|---|---|---|---|
| 直接插入排序 | $$ O(n) $$ | $$O( n^{2} )$$ | $$O( n^{2} )$$ | $$ O(1) $$ | 是 | 无关 | 有关 |
| 冒泡排序 | $$ O(n) $$ | $$O( n^{2} )$$ | $$O( n^{2} )$$ | $$ O(1) $$ | 是 | 有关 | 有关 |
| 简单选择排序 | $$O( n^{2} )$$ | $$O( n^{2} )$$ | O(n^2) | $$ O(1)$$ | 否 | 无关 | 无关 |
| 希尔排序 | null | null | null | $$ O(1) $$ | 否 | 无关 | 有关 |
| 快速排序 | $$ O(nlog_2n) $$ | $$ O(nlog_2n) $$ | $$O( n^{2} )$$ | $$ O(nlog_2n) $$ | 否 | 有关 | 有关 |
| 堆排序 | $$ O(nlog_2n) $$ | $$ O(nlog_2n) $$ | $$ O(nlog_2n) $$ | $$ O(1) $$ | 否 | 无关 | 有关 |
| 2路归并排序 | $$ O(nlog_2n) $$ | $$ O(nlog_2n) $$ | $$ O(nlog_2n) $$ | $$ O(n)$$ | 是 | 无关 | 无关 |
| 基数排序 | $$ O(d(n+r)) $$ | $$ O(d(n+r)) $$ | $$ O(d(n+r)) $$ | $$ O( r ) $$ | 是 | 无关 | 无关 |
由于希尔排序的时间复杂度是个数学难题暂未解决，故此表格暂不指出。
标签：内部,复杂度,无关,算法,nlog,2n,排序 From： https://www.cnblogs.com/LuoXia-youyu/p/17011286.html