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_2n)$
希尔排序	$O(1)$	大约为 $O(n^{1.3})$	❌
冒泡排序	$O(1)$	最好 $O(n)$ 平均 $O(n^2)$ 最坏 $O(n^2)$	稳定
快速排序	最好 $O(log_2n)$ 平均 $O(log_2n)$ 最坏 $O(n)$	最好 $O(log_2n)$ 平均 $O(log_2n)$ 最坏 $O(n)$	❌	和划分是否对称有关在所有内部排序算法中平均性能最优
简单选择排序	$O(1)$	$O(n^2)$	❌	与初始状态无关
堆排序	$O(1)$	$O(log_2n)$	❌
归并排序	$O(n)$	$O(log_2n)$	稳定
基数排序	$O(r)$	$O(d(n+r))$	稳定	r 为基数，d 为趟数，n 为元素个数