数据结构与算法基础（王卓）（29）：直接插入排序代码网站首页 技术杂谈

void InsertSort(SqList& L) 
//咱们从第一个开始，一个一个插入
{
    KeyType* i,*j;

    for (int k = 1; k <= L.length; k++)
        //遍历整个序列表（有的有序，有的无序）
    {
        if (L.r[k].key != NULL)
            L.r[0].key = L.r[k].key;
        //给哨兵赋值
        j =& L.r[k].key;

        while (1)
            //结束循环条件是什么？
        {
            if()
        }
    }
}

注：

sort：

n. 分类; 排序; 种类; 类别; 品种; 某一种(或某一类)人;
vt. 整理; 把…分类; 妥善处理; 安排妥当;

问题：

结果写到这里为我们发现：

我们可以用 j 来比较哨兵

但是无法用 j 来执行：把所有 j 及 j 之后有序序列的元素全部往后移动一位

甚至无法执行利用 j 来找到 j 前/后的元素位置

所以，对于 i 和 j ，我们不能使用（KeyType*）类型：

设定 i , j 为int 型

Project 2：

void InsertSort(SqList& L) 
//咱们从第一个开始，一个一个插入
{
    for (int i = 1; i <= L.length; i++)
        //遍历整个序列表（有的有序，有的无序）
        //在每次的循环中，k代表的是无序队列的队头
    {
        if (L.r[i].key != NULL)
            L.r[0].key = L.r[i].key;
        //给哨兵赋值
        int j = i - 1;

        while (j>=0)
            //结束循环条件是什么？
        {
            if (L.r[j].key >= L.r[0].key)
            {
                for (int a = i; a >= j; a--)
                    L.r[a].key = L.r[a - 1].key;
                L.r[j].key = L.r[0].key;
                //已经有k++，没必要i++;
            }
            else if (L.r[j].key < L.r[0].key)
                j--;
        }
    }
}

然后紧接着，我们又去参考了标准答案：（看了视频）

标准答案

注释版本：

void InsertSort(SqList& L)
{
    int i, j;
    for (i = 2; i <= L.length; i++)
        //i表示哨兵后面的第一个元素，同时也代表着每次比较的
        // 有序序列的最后一个元素

        // i 表示的是元素的位置（第几个元素）而不是位序（数组下标）
    {
        // 前面 i 表示的是元素的位置（第几个元素）而不是位序（数组下标）
        if (L.r[i].key < L.r[i - 1].key)
            // 如果第（i+1）个元素小于第（i）个元素（才开始改动）
            //其实当i表示元素的位置（第几个元素）,不是数组下标时
            //这样写才是对的，就应该这样写
        {
            L.r[0] = L.r[i];
            //就把第（i+1）个元素复制为哨兵
            for (j = i - 1; 
                //j = i - 1 从：指向每次比较的有序序列最后一个元素 开始
                L.r[0].key < L.r[j].key;
                //比较指向的元素是否大于哨兵元素
                j--)
                // 一直向前比较到最后一个大于哨兵的元素为止（<=就停止）
                L.r[j + 1] = L.r[j];
            //每次比较指向的元素大于哨兵元素，就把
            //有序序列最后一个元素【位序为j】复制到
            //（j+1）【无序序列的第一个元素；==哨兵元素】位置一次

            // 如果插入时（j+1）的元素没有备份在（j+2）的位置,数据丢失怎么办？
            // 不可能，因为根据条件判断的语句：
            // 至少原来的（j+1）的位置是要大于哨兵的，那么根据循环规则的运行：
            // 只要大于哨兵就进行备份复制的操作，所以该情形（况）不可能发生
            L.r[j + 1] = L.r[0];  
            //该语句运行的情况（阶段）：
            // 先是让所有大于哨兵的元素都已经被比较完了，比完了以后
            // 下一步操作肯定还是继续往前面（的元素）比，然后条件判断为失败，跳出循环
            // 此时我们的 j 指针指向的：
            // 是我们第一个不满足条件判别式的元素（第一个<=哨兵的元素）
            // 那么/所以，我们就在（j+1）的位置上插入该元素
        }
    }
}

无注释版本：

void InsertSort(SqList& L)
{
    int i, j;
    for (i = 2; i <= L.length; i++)
    {

        if (L.r[i].key < L.r[i - 1].key)
        {
            L.r[0] = L.r[i];
            for (j = i - 1; L.r[0].key < L.r[j].key; j--)
                L.r[j + 1] = L.r[j]; 
            L.r[j + 1] = L.r[0]; 
        }
    }
}