4.4　插入排序算法

插入排序（Insertion Sort）算法通过对未排序的数据执行逐个插入至合适的位置而完成排序工作。插入排序算法的思路比较简单，应用比较多。

4.4.1　插入排序算法

插入排序算法通过比较和插入来实现排序，其排序流程如下：

（1）首先对数组的前两个数据进行从小到大的排序。

（2）接着将第3个数据与排好序的两个数据比较，将第3个数据插入合适的位置。

（3）然后，将第4个数据插入已排好序的前3个数据中。初始数据：118 101 105 127 112

（4）不断重复上述过程，直到把最后一个数据插入合适的位置。最后，便完成了对原始数组从小到大的排序。

为了更好地理解插入排序算法的执行过程，下面举一个实际数据的例子来一步一步地执行插入排序算法。5个整型数据118、101、105、127、112是一组无序的数据。对其执行插入排序过程，如图4-6所示。

插入排序算法的执行步骤如下：

（1）第1次排序，首先对数组的前两个数据118和101排序，由于118大于101，因此将其交换。此时排序后的数据为101、118、105、127、112。

（2）第2次排序，对于第3个数据105，其大于101，而小于118，将其插入它们之间。此时排序后的数据为101、105、118、127、112。

（3）第3次排序，对于第4个数据127，其大于118，将其插入118之后。此时排序后的数据为101、105、118、127、112。

（4）第4次排序，对于第5个数据112，其大于105，小于118，将其插入105和118之间。此时排序后的数据为101、105、112、118、127。

从上面的例子可以非常直观地了解到插入排序算法的执行过程。插入排序算法在对n个数据进行排序时，无论原数据有无顺序，都需要进行n-1步的中间排序。这种排序方法思路简单直观，在数据已有一定顺序的情况下，排序效率较好。但如果数据无规则，则需要移动大量的数据，其排序效率也不高。

插入排序算法的示例代码如下：

在上述代码中，输入参数a一般为一个数组的首地址，待排序的原数据便保存在数组a中。在程序中，首先将需要插入的元素保存到变量t中。变量j表示需要插入的位置，一般就是插入数组元素的序号。设置变量j的值为i-1，表示准备将当前位置（序号为i）的数插入序号为i-1（即前一个元素）的位置。

接着，算法程序通过while循环来进行判断，如果序号为j元素的数据大于变量t（需要插入的数据），则将序号为j的元素向后移，同时变量j减1，以判断前一个数据是否还需要向后移。通过该while循环找到一个元素的值比t小，该元素的序号为j。然后，将在序号为j的下一个元素进行数据插入操作。

读者可以结合前面的插入排序算法来加深理解。这里，为了让读者清楚排序算法的执行过程，在排序的每一步都输出了当前的排序结果。

4.4.2　插入排序算法实例

学习了前面的插入排序算法的基本思想和算法之后，下面通过一个完整的例子来说明插入排序法在整型数组排序中的应用，程序示例如下：

【程序4-3】

在上述代码中，程序宏定义了符号常量SIZE，用于表征需要排序整型数组的大小。在主函数中，首先初始化随机种子，然后对数组进行随机初始化，并输出排序前的数组内容。接着，调用插入排序算法函数来对数组进行排序。最后，输出排序后的数组。

该程序的执行结果，如图4-7所示。图中显示了每一步排序的中间结果。