第八章 内部排序比较

8.6 各种内部排序算法的比较及应用

• 内部排序算法的比较

排序算法	空间效率	时间效率	稳定性	备注
插入排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏$O(n^2)$	稳定	比较依赖初始状态
折半插入排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏$O(n^2)$	稳定	比较次数约为 $O(n{\log }_{2}n)$
希尔排序	$O(1)$	大约为 $O(n^{1.3})$	❌
冒泡排序	$O(1)$	最好$O(n)$ 平均$O(n^2)$ 最坏 $O(n^2)$	稳定
快速排序	最好$O(lo{g}_{2}n)$ 平均$O(lo{g}_{2}n)$ 最坏$O(n)$	最好$O(lo{g}_{2}n)$ 平均$O(lo{g}_{2}n)$ 最坏$O(n)$	❌	和划分是否对称有关 在所有内部排序算法中平均性能最优
简单选择排序	$O(1)$	$O(n^2)$	❌	与初始状态无关
堆排序	$O(1)$	$O(lo{g}_{2}n)$	❌
归并排序	$O(n)$	$O(lo{g}_{2}n)$	稳定
基数排序	$O(r)$	$O(d(n+r))$	稳定	r 为基数，d 为趟数，n 为元素个数

• 内部排序算法的应用 - 选取排序方法需要考虑的因素 - 排序算法小结