插入排序

所谓插入排序法，就是每一步将一个待排序元素插入到已经排序元素序列中的适当位置，直到全部插入完毕。插入排序针对的是有序序列，对于杂乱无序的数组来说，首先要构建一个有序序列，将未排序的元素插入到有序序列的特定位置，构成一个新的有序序列，再次将未排序的元素插入到有序序列的特定位置…以此类推，直到所有元素都插入到有序的序列中，排序就完成了。下面以升序排列为例，分步骤讲解插入排序的过程。

第1步：从第1个元素开始，将其视为已排序的元素。

第2步：取下一个元素（待排序元素），与左边已排序的元素相比较，如果已排序元素大于待排序元素，则将已排序元素向后移动，将待排序元素插入到已排序元素的前面。

第3步：如果已有多个元素有序，则将待排序元素自右向左逐个与有序元素进行比较，直到有序元素小于待排序元素，然后将有序元素向后移动，将待排序元素插入到小于它的元素后面。

第4步：再取下一个待排序元素，重复上述步骤，直到所有元素都排序完毕。

插入排序的过程类似于打扑克摸牌过程，摸到第1张牌时，将其看作一个有序序列；摸到第2张牌时，如果它比第1张牌大就将其插入到第1张牌后面，否则插入到第1张牌前面；摸到第3张牌，就扫描前两张牌，选择适当的位置插入…，以此类推，直到摸牌完毕，手里的牌就是一个有序序列。

插入排序的流程可用图1描述。

图1 插入排序（以升序排列为例）

仍旧以数组{9,8,3,5,2}为例，使用插入排序调整数组顺序的过程如图2所示。

图2 插入排序过程

在图2中，以数组的第1个元素9为基准，取下一个元素8与之比较，因为8<9，则将8插入到9的前面，即将9与8互换位置，这样，构建了一个新的有序序列。再取下一个元素3，与9比较，因为3<9，则将9向后移动，将9的位置空出来，然后再将3与8比较，因为3<8，则将8向后移动，将3插入到8所在的位置，这样前三个元素又构成一个新的有序序列。以此类推，直到整个序列排序完成。

需要注意的是，当有元素向后移动时，只是有序元素向后移动，要插入的元素一直保存在临时变量中。例如，在图2中，将元素3插入到8、9构成的有序序列中，3与9比较之后，由于3<9，因此元素9向后移动，空出位置，此时3并不是插入到元素9空出的位置中，而是继续与前面的元素8比较，由于3<8，因此元素8向后移动到元素9之前所在的位置，元素3插入到元素8空出的位置中。该过程如图3所示。

图3 元素3插入排序过程

理解了插入排序的原理与过程，代码实现就很容易了，插入排序的代码实现如例1所示。

例1 intsertSort.c

 1  #include <stdio.h>
 2  int main()
 3  {
 4    int arr[5] = { 9,8,3,5,2 };
 5    int i, j, temp;
 6    printf("排序之前：");
 7    for (i = 0; i < 5; i++)
 8      printf("%d\t", arr[i]);
 9    for (i = 1; i < 5; i++)  //i从1开始，假设0角标上的元素是有序的
 10   {
 11     temp = arr[i];     //用temp记录i位置上的元素
 12     j = i;         //j记录i角标
 13     //如果有序元素大于i元素，就将有序元素下移
 14     while (j > 0 && arr[j - 1] > temp) 
 15     {
 16       arr[j] = arr[j - 1];//有序元素下移
 17       j--;        //j自减，但要保证j>0,判断左边是否有多个有序元素
 18     }
 19     arr[j] = temp;     //将i元素插入到适当位置j
 20   }
 21   printf("\n排序之后：");
 22   for (i = 0; i < 5; i++)
 23     printf("%d\t", arr[i]);
 24   return 0;
 25 }

例1运行结果如图4所示。

图4 例1运行结果