直接插入排序比较次数

对于直接插入排序算法，最坏情况下的比较次数为 $\frac{n(n-1)}{2}$，其中 $n$ 是待排序序列的长度。在最优情况下，即待排序序列已经有序，比较次数仅为 $n-1$。平均情况下的比较次数大约为 $\frac{n^2}{4}$。需要注意的是，直接插入排序的时间复杂度不仅取决于比较次数，还与移动数据的次数有关。