直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。
顾名思义,从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。
/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L){
int i, j;
for (i = 2; i <= L->length; i++){
/* 需将L->r[i]插入有序子表 */
if (L->r[i] < L->r[i - 1]){
/* 设置哨兵 */
L->r[0] = L->r[i];
for (j = i - 1; L->r[j] > L->r[0]; j--)
/* 记录后移 */
L->r[j + 1] = L->r[j];
/* 插入到正确位置 */
L->r[j + 1] = L->r[0];
}
}
}
- 程序开始运行,此时我们传入的SqList参数的值为length=6,r[6]={0,5,3,4,6,2},其中r[0]=0将用于后面起到哨兵的作用。
- 第4~13行就是排序的主循环。i从2开始的意思是我们假设r[1]=5已经放好位置,后面的牌其实就是插入到它的左侧还是右侧的问题。
- 第6行,此时i=2,L.r[i]=3比L.r[i-1]=5要小,因此执行第8~11行的操作。第8行,我们将L.r[0]赋值为L.r[i]=3的目的是为了起到第9~10行的循环终止的判断依据。如图9-5-2所示。图中下方的虚线箭头,就是第10行,L.r[j+1]=L.r[j]的过程,将5右移一位。
- 此时,第10行就是在移动完成后,空出了空位,然后第11行L.r[j+1]=L.r[0],将哨兵的3赋值给j=0时的L.r[j+1],也就是说,将扑克牌3放置到L.r[1]的位置,如图9-5-3所示。
- 继续循环,第6行,因为此时i=3,L.r[i]=4比L.r[i-1]=5要小,因此执行第8~11行的操作,将5再右移一位,将4放置到当前5所在位置,如图9-5-4所示。
- 再次循环,此时i=4。因为L.r[i]=6比L.r[i-1]=5要大,于是第8~11行代码不执行,此时前三张牌的位置没有变化,如图9-5-5所示。
- 再次循环,此时i=5,因为L.r[i]=2比L.r[i-1]=6要小,因此执行第8~11行的操作。由于6、5、4、3都比2小,它们都将右移一位,将2放置到当前3所在位置。如图9-5-6所示。此时我们的排序也就完成了。