插入排序基本原理

---

每次从【未排序】中选取第一个元素放置到【已排序】的正确位置

版本1：直接开辟n的空间

版本2：直接插入排序，无哨兵

Sort::DirectInsertionSort_2() {
    int tmp;
    /*从[1]开始，[0]已经有序了*/
    for(int i = 1; i < sorted.size(); i++) {
        /*反之，[i]的位置本来就是正确的，不需要交换*/
        if(sorted[i] < sorted[i-1]) {
            tmp = sorted[i];
            moveTimes++;
            int j = i - 1;
            /*每次循环把[i]插入到[0:i-1]的正确位置*/
            for(; j >= 0 && tmp < sorted[j]; j--) {
                compareTimes++;
                sorted[j+1] = sorted[j]; //后移
                moveTimes++;
            }
            compareTimes++;
            sorted[j+1] = tmp;
            moveTimes++;
        }
    }
}

参考

---

直接插入排序（哨兵和越界）
白话经典算法系列之二 直接插入排序的三种实现