Question

直接插入排序算法中的疑问

最近在看《大话数据结构》中关于直接插入排序算法

1 void InsertSort(SqList *L)
2 {
3 int i,j;
4 for(i=2;i<=L->length;i++)
5 {
6 if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */
7 {
8 L->r[0]=L->r[i]; /* 设置哨兵 */
9 for(j=i-1;L->r[j]>L->r[0];j--)
10 L->r[j+1]=L->r[j]; /* 记录后移 */
11 L->r[j+1]=L->r[0]; /* 插入到正确位置 */
12 }
13 }
14 }

其中第11行为什么要将哨兵赋值给L->r[j+1] ？而不是L->r[j]？？

Answer 1

你只是对链表中的一个节点中的一个数组r进行排序，那么其实就是对一个数组排序，和链表没有关系
那么就是简单的对一个数组排序，插入排序其实很简单的思路，

就是判断这个要插入的数据的位置，让这个位置后面的数据都后移一个位置
9 for(j=i-1;L->r[j]>L->r[0];j--)
10 L->r[j+1]=L->r[j];
从后面开始判断，如果r[j]>r[0]，那么就后移一个位置，给要插入的数据倒出一个位置来

最后把数据插入到不大于要出入的数据的那个位置。

11 L->r[j+1]=L->r[0];
这个就是赋值了，也就是把r[0]插入到那个倒出的位置

这么说明白了吧
这就是插入排序，两层循环

Answer 2

注意，第11的语句没有包括在里层的for循环里，所以在里层for循环最后一次执行时，j--了一次
然后在执行第十一句，相当于是赋值给L->r[j]。

Answer 3

因为在9行的for循环中，默认只执行10行语句，且有L->r[j]>l->r[0]约束，所以j递减至0循环结束，此时记录后移只到达L->r[2]=L->r[1];并未包括L->r[1]=L->r[0],所有11行如此写

Answer 4

j--了次。