插入排序算法算法设计

插入排序算法的基本思想是每次将一个待排序的元素，按其大小插入到已经排好序的子序列的适当位置，直到全部元素插入完成为止。具体实现时，插入排序会将序列分为两部分：头部是已经排序完毕的，尾部是待排序的状态。从头开始扫描每一个元素，每当扫描一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序。插入排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。

以下是Java实现插入排序算法的代码：

public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < arr.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }
}