各种插入排序算法小结

直接插入排序是将元素vec[i]插入到有序序列vec[0..i-1]， 依次将vec[i]与vec[i-1]，vec[i-2]，...进行比较，找到插入位置即将vec[i]插入，原来位置上的对象向后顺移。
直接插入算法代码如下：
void InsertSort_1(int vec[], int n) //直接插入排序
{
     int i, j;
     int temp;
     
     for (i=1; i<n; i++)
     {
         temp = vec[i];
         for (j=i;(j>0) && (vec[j-1]>temp); j--)
         {
             vec[j] = vec[j-1];
         }
         vec[j] = temp;
     }
}

直接插入法在查找插入位置时采取逐一比较的方法，效率较低，为了提高查找效率，可采用折半查找法。代码如下：
void InsertSort_2(int vec[], int n) //折半插入排序
{
     int i, j, low, high, mid;
     int temp;
     
     for (i=1; i<n; i++)
     {
         temp = vec[i];
         low = 0;
         high = i-1;
         while (low <= high) //折半查找插入位置
         {
             mid = (low + high)/2;
             if (vec[mid] > temp)
             {
                 high = mid -1;
             }
             else
             {
                 low = mid + 1;
             }
         }
         //进行插入操作
         for (j=i; j>low; j--)
         {
             vec[j] = vec[j-1];
         }
         vec[low] = temp;
     }
}

插入排序在对几乎已经排好序的数据操作时，效率高，几乎可以达到线性排序的效率，但进行插入操作时，每次只能将数据移动一位，难免出现大量重复移动，如果能将元素尽可能快的移动到它“该去”的地方，将大大减少重复移动的次数，提高效率。
希尔排序是把全部元素分组排序，将所有距离为步长gap的元素放在同一个组中，通过“跳跃式移动”的方法，能让元素每次移动一大步，即步长gap>1，大大提高了移动的效率。一趟排序下来，虽然同组的元素没有挨在一起，各组元素相互隔开，但是由于每一组都已经各自排好序了，所以整个序列还是“基本有序”的。
然后再取越来越小的步长进行排序，直到步长gap=1时，就是普通的插入排序，但是到了这步，整个序列是“基本有序”了，直接插入排序也能高效完成。
代码如下：
void ShellSort(int vec[], int n) //希尔排序
{
     int i, j, gap;
     int temp;
     
     for (gap=n/2; gap>0; gap/=2)
     {
         for (i=gap; i<n; i++)
         {
             temp = vec[i];
             for (j=i; (j>=gap) && (temp<vec[j-gap]); j-=gap)//跳跃插入，跳跃距离为gap
             {
                 vec[j] = vec[j-gap];
             }
             vec[j] = temp;
         }
     }
}

希尔排序的关键在于不能将元素随便分组后各自排序，而是将相隔一定步长的元素组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长串行都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
Donald Shell 最初建议步长选择为n/2，并且对步长取半直到步长达到 1。虽然这样取可以比O(n2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式。这项研究也表明"比较在希尔排序中是最主要的操作，而不是交换。"用这样步长串行的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
另一个在大数组中表现优异的步长串行是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）。
*/