插入排序

用图说话

插入排序图解

放码过来C++

// 插入排序
void insertionSort(vector<int> array)
{
    /*
    算法思想：根据插入排序的思想，将数组分成两个部分，一个是有序一个是待插入，
            然后拿待插入的每一个元素去跟有序数组的每一个元素比较
            ok，这里就有大概的思路了，拿待插入的每一个元素，那我这里得用一个循环来遍历
            跟有序数组的每一个元素比较，这里还得一个循环来遍历有序数组
            那么我脑海中大概的代码就是酱紫了
             for(待插入的数组) {
                 for(有序数组) {
                     处理待插入和有序数组的比较的
                 }
             }
           ok，有了这个思路后，我们就开始一步一步撸，慢慢调了
     */
    
    // *** 开始撸,对着我做的图来看比较容易理解哦！ ***/
    
    // 遍历待插入数组；
    // 之所以i从1开始，是因为默认数组的第一个元素的有序的
    for (int i=1; i<array.size(); i++) {
        // 取待插入数组的第一个元素
        // i表示待插入数组的第一个元素下标
        // kmp表示待插入数组的第一个元素
        int kmp = array[i];
        // i-1 就是有序数组的最后一个元素
        int j = i-1; // 为什么要设置这个j呢，因为下面有while() 要把这个j作为循环的终止条件
        // 当待插入元素kmp小于有序数组的最后一个元素时，这个有序数组的最后一个元素后移
        // kmp即将要插入的值
        // 为什么j>=0 因为比如9 3 4 2其中9 3 4 是有序数组，2是即将要插入的值，那么这时候2跟9比较
        // 也就是kmp = 2 Array[j] == 9，则j == 0；所以j == 0是要进入循环的，所以j>=0
        // 这个while循环的作用就是拿待插入值跟有序数组元素一一比较，然后大于就让有序数组的元素后移，最后将要插入值的位置空出来
        while (j>=0 && kmp<array[j]) {
            // 后序数组元素后移
            array[j+1] = array[j];
            j--;
        }
        // 当比较完之后，将这个即将插入的值kmp，插入到指定的数组位置中
        array[j+1] = kmp;
        // 为什么是j+1 举个例子
        // 比如9 3 4 2其中9 3 4 是有序数组，2是即将要插入的值，那么这时候2跟9比较
        // 也就是(kmp == 2) < (array[j==0] == 9) 那么满足条件，进入循环，进入之后，9后移，j--，这时候j--后就等于-1了
        // 所以我这个即将要插入的值kmp，应该插入下标为0的位置，但是这时候的j==-1，所以array[j+1] = kmp
    }
    
}

code地址

https://github.com/ChenZeBin/TheDataStructureByUsingCpp.git