《大话数据结构》第9章 排序 9.5 直接插入排序
9.5.1 直接插入排序算法
扑克牌是我们几乎每个人都可能从事过的游戏。而最基本的扑克玩法都是一边摸牌，一边理牌。假如我们拿到了这样一手牌，如图9-5-1。啊，似乎是同花顺呀，别急，我们得理一理顺序才知道是否是真的同花顺。请问，如果是你，应该如何理牌呢？
应该说，哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。（注：要了解算法的原理，直接看代码和后面的解释并不是最好的办法。将代码输入到电脑中，运行并断点逐行跟踪，参照本文的讲解和图示，观察变量的变化情况，才会收到比较好的效果。这里的代码全是用C语言编写，不过对于擅长C#的读者应该不存在阅读难度。）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 }1) 程序开始运行，此时我们传入的SqList参数的值为length=6,r[6]={0,5,3,4,6,2}，其中r[0]=0将用于后面起到哨兵的作用。
2) 第4～13行就是排序的主循环。i从2开始的意思是我们我们假设r[1]=5已经放好位置，后面的牌其实就是插入到它的左侧还是右侧的问题。
3) 第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右移一位。
4) 此时，第10行就是在移动完成后，空出了空位，然后第11 行L.r[j+1]=L.r[0]，将哨兵的3赋值给j=0时的L.r[j+1]，也就是说，将扑克牌3放放置到L.r[1]的位置。如图9-5-3。
5) 继续循环，第6行，因为此时i=3，L.r[i]=4比L.r[i-1]=5要小，因此执行第8～11行的操作。将5再右移一位，将4放置到当前5所在位置。如图9-5-4。
