插入排序

基本思想:每次将一个待排序的记录按照关键吗从小到大的顺序插入前面已经排好序的子文件中,直至全部的记录插入完成为止.

插入排序有两种排序,一是基本插入排序,一是希尔(SHELL)排序.

一.基本插入排序:

基本思想:将待排序序列分成已排序和未排序两部分.初始时,R[1]自成已排序.插入时,从R[2]开始到R[N]为止,依次将R[I]插入到已排序的部分中.插入位置K按照下面的算法来处理,对于R[I]来说,从R[1]到R[I-1]找到一个位置K,使得R[i]插入后,R[K]比R[1]-R[K-1]都大,比R[K+1]-R[I-1]都小.具体插入时,从R[K]-R[I-1]都往后移动一个位置,在K上插入R[I];如果R[I]比R[1]-R[I-1]都小,则R[I]保持不动.直到全部待排序数组全部插入为止.

二.希尔(SHELL)排序

基本思想:对于无序集合R[1]-R[N],先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

2．Shell排序的时间性能优于直接插入排序，据统计分析其时间复杂度为O(n^1.3)

　　希尔排序的时间性能优于直接插入排序的原因：

　　①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

　　②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n^2)差别不大。

　　③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

　　因此，希尔排序在效率上较直接插人排序有较大的改进。

　　3．稳定性

　　希尔排序是不稳定的。