精华：算法总结归纳区别复盘：

目录

精华：算法总结归纳区别复盘：

标准答案思路：

我的答案思路：

区别和问题：

（1）：

只有【无序序列的第一个元素（哨兵）】小于【有序序列最后一个元素】时

我们才启用哨兵

（2）： while (j>0)不是一个合格的循环的判断语句

（3）：只需要把【有序序列最后一个元素】复制到【无序序列的第一个元素】位置一次就可以

（4）：i 是表示元素的位置（第几个元素）还是位序（数组下标），其实都可以

根据上述问题的表述，又重新写出第一个修正版本的程序：

仍然存在问题：

（5）：在判断语句  while (L.r[j].key >= L.r[0].key)之前，没有对哨兵进行赋值

（6）：这个时候对于何时使用哨兵，如何确定条件范围又成为了一个新的问题

（7）：【哨兵元素】小于【我们比较的元素】情况的语句不应该是

（8）： j = i - 1 应改为：j = i（存疑）

（9）：注意while循环的两语句前后顺序不可以颠倒

（10）：为什么最后一步插入元素的操作采用【j + 1】

个人版本最终答案:

---

---

标准答案思路：

第一次从第二个元素开始逐个往后遍历

每次遍历时从第几（i）个开始，就记：

开始及开始前面的几（i）个元素都是有序序列

如果【无序序列的第一个元素】小于【有序序列最后一个元素】，使用哨兵

第（i + 1）个元素 小于第（i）个元素

从：指向每次比较的有序序列最后一个元素（i） 开始

比较指向的元素是否大于哨兵元素，若是，则：

把【有序序列最后一个元素】复制到【无序序列的第一个元素】位置一次

把（j）复制到（j + 1）【 == 哨兵元素】

比较指向的前面一位元素是否大于哨兵元素若是，则重复上述循环操作

一直向前比较直到（比较到）最后一个大于哨兵的元素为止（ <= 就停止）
 

把哨兵元素插入在：

最后一个大于哨兵的元素之前
第一个小于哨兵的元素之后

---

我的答案思路：

比较哨兵（位序为0的）元素和指针 j 指向的元素

若大于等于：（哨兵元素大于等于指针 j 指向的元素）
【交换元素】

把所有 j 及 j 之后有序序列的元素全部往后移动一位

（因为要插入的新元素已经放在哨兵里面了，我们不用担心后退一位会不会有数据丢失的影响）

把哨兵元素插入到指针 j指向的位置
 

若小于：（哨兵元素小于指针 j 指向的元素）
【继续比较，和前面一位比较】

j--;

---

区别和问题：

（1）：

只有【无序序列的第一个元素（哨兵）】小于【有序序列最后一个元素】时

我们才启用哨兵

这样的写法更加高效一点

---

（2）： while (j>0)不是一个合格的循环的判断语句

难不成我们每次比较的循环都必须要比较到底不成？？？

 这里我们突然就意识到了：

实际上我们只有在：【哨兵元素】小于【我们比较的元素】的时候，才进行复制备份和插入的操作

所以循环条件应改为：

        while (L.r[j].key >= L.r[0].key)

 没必要写

            else if (L.r[j].key < L.r[0].key)
                j--;

---

（3）：只需要把【有序序列最后一个元素】复制到【无序序列的第一个元素】位置一次就可以

我的思路中：

每次只要【无序序列的第一个元素（哨兵）】小于【有序序列最后一个元素】

都把有序序列这个元素后面的元素全部往后移动一位

---

没必要，浪费了时间

只需要：

把【有序序列最后一个元素】复制到【无序序列的第一个元素】位置一次

就可以

---

为什么这样不会出问题：

实际上我们的算法在操作时

先在每一次后面的元素都已经复制备份一遍以后，然后再看下一个元素是否需要复制备份

不用担心前面有没有元素没有备份过，这是个伪命题

---

（4）：i 是表示元素的位置（第几个元素）还是位序（数组下标），其实都可以

我们可以根据程序的不同需求设定调整程序

---

根据上述问题的表述，又重新写出第一个修正版本的程序：

void InsertSort(SqList& L) 
{
    int i;
    for (i = 1; i < L.length; i++)
        //i代表的是位序
    {
        int j = i - 1;
        while (L.r[j].key >= L.r[0].key)
        {
            L.r[0].key = L.r[i].key;
            L.r[j + 1].key = L.r[j].key;
            j--;
        }
        L.r[j + 1].key = L.r[0].key;
    }
}

仍然存在问题：

---

（5）：在判断语句  while (L.r[j].key >= L.r[0].key)之前，没有对哨兵进行赋值

也就是说，实际上这个时候哨兵根本不存在

---

（6）：这个时候对于何时使用哨兵，如何确定条件范围又成为了一个新的问题

（其实这里面我们的思路思维做法是参照根据了标准答案的做法倒推而来的）

首先，既然我们是进行逐个向后遍历的操作，那么/也就是说：

肯定是发生了不一样的情况/出了问题，我们才对目标对象进行特殊/不一样的操作：

所以这里的情况肯定就是：

队列不再保持之前有序的性质，出现了一个：

后面的一个元素小于前面的一个或多个元素的情况

而这时我们应对这种情况所做出的所对应的操作算法范围，肯定不止一个简单的哨兵赋值的操作

重新参考前面设计的思路，直接插入的全部算法操作：

把【有序序列最后一个元素】复制到【无序序列的第一个元素】位置/把所有 j 及 j 之后有序序列的元素全部往后移动一位

把哨兵元素插入在：
最后一个大于哨兵的元素之前
第一个小于哨兵的元素之后

显然都在该情况范围之内

---

（7）：【哨兵元素】小于【我们比较的元素】情况的语句不应该是

        if (L.r[i].key < L.r[i - 1].key)

应改为：

        if (L.r[i + 1].key < L.r[i].key)

因为我们需要的情况是：

【哨兵元素】小于【我们比较的元素】

对应到元素的位置，就是：

第（ i ）个小于第（i - 1）个

对应到数组内部位序，就是：

【i + 1】小于【 i 】

---

（8）： j = i - 1 应改为：j = i（存疑）

j 表示指向的元素的位序，那么， j 的起始/初始值就应该向 i 看齐

至于前面的标准答案为什么是 j = i - 1：

前面的标准答案 i 表示的是元素的位置（第几位）

存疑：

Github上面的版本虽然 i 也是从1开始，但是他用的也是 i - 1；

---

（9）：注意while循环的两语句前后顺序不可以颠倒

同时在这里趁着这个机会，我们也温习一下 for语句的语序执行流程：

for([表达式1]；[表达式2]；[表达式 3]）语句a

执行顺序：

1. 解表达式1
2. 解表达式2，若真（非 0）：
3. 执行语句a【for语句中指定的内嵌语句(即最后的语句)】
4. 解（执行）表达式3

---

（10）：为什么最后一步插入元素的操作采用【j + 1】

原因和前面标准答案为什么使用【j + 1】类似（相同）

这里不再赘述

---

个人版本最终答案:

void InsertSort(SqList& L) 
{
    for (int i = 1; i < L.length; i++)
        //i代表的是位序
    {
        int j = i;
        if (L.r[i + 1].key < L.r[i].key)
        {
            L.r[0].key = L.r[i].key;
            while (L.r[j].key >= L.r[0].key)
            {
                L.r[j + 1].key = L.r[j].key;
                j--;
            }
            L.r[j + 1].key = L.r[0].key;
        }
    }
}

---

算法时间复杂度：O(n^2)，空间复杂度：O(1)

---

以上