选择排序

插入排序

比较的总次数是交换的次数加上一个额外的项：因为一路向左比，假设比它大的元素有 M 个，最后还要比一次以确定第 M+1 个元素比它小。

插入排序适合部分有序数组和小规模数组。

插入排序 vs 选择排序

希尔排序

希尔排序利用了插入排序适合部分有序数组和小规模数组的特点。