下载掌阅APP，畅读海量书库
立即打开
插入排序比冒泡排序和选择排序更容易理解，采用与整理物品相同的思路，每次排序都是将一个新的元素插入到已经有序的序列中，只要玩过扑克牌的人都能立刻理解该算法。
插入排序的基本思想如下。
（1）与前两种排序算法相同，将序列分为无序区和有序区两部分，无序区存放尚未处理好的数据，有序区存放已经按关键字排序后的数据，通常有序区在前、无序区在后。
（2）初始时，将待排序序列中的第1个元素存入有序区（只有一个元素当然有序），由其余待排序数据构成无序区。
（3）每轮排序中，在无序区中选择第1个元素作为基准元素，同时保存至哨兵key中，从尾至头向前扫描有序区，寻找该元素在有序区的最终位置。若其关键字小于有序区当前元素，则将有序区当前元素向后移动一个位置（基准元素的位置已经腾出），找到相应位置后将key插入该位置。
（4）重复执行（2）和（3），直至无序区只有一个元素为止。
设待排序的无序序列存放于数组array中，长度为length，给出插入排序的伪代码如表2-3所示。
表2-3 插入排序的伪代码
假定待排序的数据为｛10，1，35，61，89，36，55｝，7个元素最多需要进行6趟排序。排序的原则是将无序区的首元素插入到有序区中的合适位置，排序过程如图2-4所示。
图2-4 插入排序的过程
有序区 d =｛10｝，无序区 r =｛1，35，61，89，36，55｝。
第一趟排序：无序区起始位置 i =1，首元素值key=1，有序区元素从尾向头比较，key<10，10需要向后移动一个位置。此时，有序区空，下标为0的位置即为key在有序区的最终位置，将key移到该位置。此时，有序区 d =｛1，10｝，无序区 r =｛35，61，89，36，55｝。
第二趟排序：起始位置 i =2，首元素值key=35，从有序区尾部向头部比较，key>10，无须移动元素，key已经在最终位置。此时，有序区 d =｛1，10，35｝，无序区 r =｛61，89，36，55｝。
第三趟排序：起始位置 i =3，首元素值key=61，自有序区尾部向头部比较，key>35，无须移动元素，key已经在最终位置。此时，有序区 d =｛1，10，35，61｝，无序区 r =｛89，36，55｝。
第四趟排序：起始位置 i =4，首元素值key=89，自有序区尾部向头部比较，key>61，无须移动元素，key已经在最终位置。此时，有序区 d =｛1，10，35，61，89｝，无序区 r =｛36，55｝。
第五趟排序：起始位置 i =5，首元素值key=36，自有序区尾部向头部比较，key<89、key<61、key>35，89和61依次向后移动一个位置。此时，原61所在的下标位置3即为key的最终位置，将key移到该位置。合并key至有序区后，有序区 d =｛1，10，35，36，61，89｝，无序区 r =｛55｝。
第六趟排序：起始位置 i =6，首元素值key=55，自有序区尾部向头部比较，key<89、key<61、key>36，89和61依次向后移动一个位置。此时，原61所在的下标位置4即为key的最终位置，将key移到该位置。合并key至有序区后，无序区 r =｛｝，合并后有序区 d =｛1，10，35，36，55，61，89｝。
此时，所有待排序元素已经合并至有序区，无序区空，排序过程结束。
实现插入排序主体功能的是insertion_sort（）函数，main（）函数用于测试排序的效果。insertion_sort（）函数可实现对部分序列进行排序，包括3个参数，data［］为待排序数组，start为排序区间的起始下标，len为待排序区间的长度。
insertion_sort（）函数实现区间数据升序排序时，有序区在前，无序区在后。初始时，有序区的第一个元素为data［start］，无序区为data［start+1，start+2，…，start+len-1］。因此，排序从start+1开始，到start+len-1结束。
每轮排序时，选择无序区的第1个元素（即下标为i的元素）作为待处理元素并保存在key中，在有序区中从尾（i-1）向头寻找key的最终位置。若当前元素data［j］>key且在有序区范围内时，将有序区当前元素data［j］向后移动一个位置，直至找到最终位置后将key插入到该位置。
实现代码如下。
测试数据及运行结果如下。
①数据总数及各数据：
7
10 1 35 61 89 36 55
②待排序的起始位置及排序长度：
0 7
③运行结果：
1 10 35 36 55 61 89
