7.3 入排序★2◎3

　　7.3 插入排序★2◎3

　　插入排序算法与上述最根本的不同点，就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。
　　1．直接插入排序
　　设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关键码有序。即
　　r[1].key≤r[2].key≤……≤r[n].key
　　实现“一趟直接插入排序”可分3步进行：
　　①在r[1，…，i-1]中查找R[i]的插入位置，r[1，…，j].key≤r[i].key <r[j+1，…，i-1].key；
　　②将r[j+1，…，i-1]中的所有记录均后移一个位置；
　　③将r[i] 插入（复制）到r[j+1]的位置上。
　　在有序表{2,10,18,25}中插入一个元素9的过程如下：

　　直接插入排序方法：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。
　　【效率分析】
　　空间效率：仅用了一个辅助单元。
　　时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。
　　在最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较和0次移动。总比较次 数=n-1次，总移动次数=0次。
　　在最坏情况下：即第i趟操作，插入记录需要和前面的i个记录进行i次关键码比较，移动记录的次数为i+1次。

　　
　　在平均情况下：在等概率下，总比较次数和移动次数可取最好情况和最坏情况的平均数，均约为次。
　　由此，直接插入排序的时间复杂度为 ，是一个稳定的排序方法。
　　2．折半插入排序
　　直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定是通过对有序表的顺序查找得到的。而折半插入排序的基础思想是在有序表中通过折半查找确定插入位置，平均情况下总比较次数约为n2/4。既然是在有序表中确定插入位置，就可以不断二分有序表来确定插入位置。通过待插入记录与有序表中的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一轮便确定了插入位置。
　　实现“一趟折半插入排序”可分3步进行：
　　①在r[1,…, i-1]中折半查找r[i]的插入位置，r[1,…, j].key ≤r[i].key <r[j+1,…,i-1].key；
　　②将r[j+1,…,i-1]中的所有记录均后移一个位置；
　　③将r[i]插入（复制）到r[j+1]的位置上。
　　向有序表{2，10，18，25}中折半查找插入一个元素9的过程如下：

　　【效率分析】
　　辅助空间与直接插入排序相同，确定插入位置所进行的折半查找，关键码的比较次数最多为次；移动记录的次数和直接插入排序相同，故时间复杂度仍为，是一个稳定的排序方法。