插入类排序的C语言实现

        插入类排序包括直接插入排序、折半插入排序、希尔排序三种。

直接插入排序

        直接插入排序，Straight Insertion Sort，是一种最简单的排序方法，它的基本思想就是把一个序列分为有序和无序两部分，把无序部分的记录逐个插入到一个有序的部分中，其基本步骤可以概括为两步：一是取出一个元素，留出空位；二是符合条件的元素右移，把取出的元素插入。那么这样的话，我们就需要一个辅助的变量来临时缓存这个被取出的变量，一般我们把这个辅助变量称之为“哨兵变量”。

        1、一开始，第一个数肯定是有序，后续部分为无序，从无序部分取出第一个数为哨兵变量。

         2、取出哨兵变量之后，在有序部分进行比较，寻找合适的位置插入，在例子中，合适位置就是其原来的地方，直接插入，然后有序部分就多了一个元素。

         3、再依次从无序部分取出元素，在有序部分逐个寻找合适位置，若遇到符合条件的元素，就将其右移，例如在取出3这个元素时，此时有序部分是2 5 8，在有序部分逐个比较，8比3大，此时就需要将8向后移，然后比较5,5比3大，再将5向后移，再比较2，2比3小，比较停止，在此处插入3。从第二个元素开始对所有元素重复进行上述步骤即可全部排序，总计需要进行size - 1次。

        代码部分，排序是从第二个元素开始的，所以直接定义i = 1,为了简便，只给出3的排序过程。以升序为例。

         此时有序部分为2 5 8，i = 3,哨兵变量为tmp = 3,之后从有序部分的最后一个元素开始逐个比较，所以j = i - 1;然后进行8和3的比较，8 > 3，不符合升序，需要将8向后移。然后比较下一个，所以j向前移。

         此时比较5和3,5 > 3，不符合升序，需要将5向后移，然后比较下一个，所以j要前移。

        此时比较2和3，2 < 3，需要将3放置到2的后边才符合升序，此时j = 0，正确的插入位置在j+1处。

         所以就完成了3的排序，从上述示例中可以得出循环的条件，要在升序中，要满足tmp < a[j],当tmp不满足时，循环终止，j+1处就是正确插入位置。

        若哨兵变量是最小的元素呢？有序部分的元素全部都比哨兵变量大，此时j会逐渐向前移动，直到j = 0处仍然没有跳出循环，j最终会等于-1，发生了溢出。由于哨兵变量是最小的元素，理应插入到最左边，也就是下标为0的位置，正确插入位置仍然为j+1,。所以循环条件还需要满足j>=0。

void sort(int *a,int len)
{int i,j;//循环从1开始，第二个元素开始和前面比较for (i = 1; i < len; i++){//只有当该元素小于前面的元素才执行排序//因为前面的元素已经有序，若当前元素已经符合其顺序，自然不用再排序if(a[i] < a[i - 1]){//取出该元素（哨兵）int tmp = a[i];j = i - 1;//和前面的元素进行比较，j从i - 1开始向前//修改排序方向只需要修改此处的比较符号，下面以从小到大排序为例//必须满足j >= 0，表示数组不会溢出//若该元素小于前面的元素，不符合升序，则将前面的元素向后移//又因为该元素已经取出，前面的元素也依次后移，不用考虑丢失问题。//当该元素大于前面的元素时，就符合升序了，找到了正确的插入位置，循环终止while (j >=0 && tmp < a[j]){a[j + 1] = a[j];j--;}//将该元素插入//循环终止之后，下标为j+1的位置才是正确的插入位置//因为tmp是和下标为j的元素比较所以跳出循环的，应该在其后面插入。//若是j导致循环终止，此时j为-1，数组已经发生溢出，更要+1.//下一个元素在之前已经后移了，所以不需要考虑后一个元素丢失。a[j + 1] = tmp;}//打印每次排序的结果for (j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}
}

折半插入排序

        折半插入排序是对直接插入排序的一种改良方式，在直接插入排序中，每次向已排序序列中插入元素时，都要去寻找插入元素的合适位置，但是这个过程是从已排序序列的最后开始逐一去比较大小的，这其实很是浪费，因为每比较一次紧接着就是元素的移动。折半排序就是通过折半的方式去找到合适的位置，然后一次性进行移动，为插入的元素腾出位置。什么是折半的方式去找合适的位置呢，那就是折半查找了，因为再已排序的序列中，序列元素都是按照顺序排列的，既然这样，完全不需要逐一去比较大小，而是去比较已排序序列的中位数，这个中间的位置将一排序列分为左右两部分，通过一次比较后，就缩小了比较的范围，重复这样的操作，需要插入的元素就找到了合适的位置了。

        也就是说，折半插入排序和直接插入排序的思路大致相同，只是在寻找合适位置时，折半插入使用了二分查找的方式提高了效率，减少了比较的次数，但是并没有减少移动的次数，因此时间复杂度和直接插入排序相同，但折半插入排序的常数项更小。

void half_sort(int *a,int len)
{//从小到大排序for (int i = 1; i < len; i++){//先将插入的该元素保存int tmp = a[i];//定义有序列表的两端下标int high = i - 1,low = 0;//二分查找，定义中间下标int mid = (high + low) / 2;//设置循环条件，当两端下标不符合正常的low<=high时跳出循环while (low <= high){//计算中间下标mid = (high + low) / 2;//若该元素大于中间元素，则需要向高端靠拢，使low等于中间下标+1，就舍弃了原来的[low,mid]范围，缩小了一半的查找范围if(tmp > a[mid])low = mid + 1;else//该元素小于中间元素，则需要向低端靠拢，使high等于中间下标-1，就舍弃了原来的[mid,high]范围，缩小一半的查找范围high = mid - 1;}//最终high+1或者low（high和low满足high + 1 = low）是要插入的位置//将high+1或者low之后的有序列表向后移动for (int j = i; j > low ; j--){a[j] = a[j - 1];}//在正确位置插入该元素a[low] = tmp;//打印每次排序的过程for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}
}

        注意上述代码的排序稳定性，这里的if条件要加等号，否则就是不稳定的排序。

if(tmp >= a[mid])low = mid + 1;
elsehigh = mid - 1;

        以升序为例，若tmp = a[mid];加了等号，就会使low向右移，最终插入到其右边。排序的稳定性要求相同的元素不改变原有位置，tmp本来就是从无序部分取出的，在其右边，最终也应该插入到右边。

希尔排序

        希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

        直接插入排序在序列基本有序时，在序列长度较小时效率高，基于此思想就提出了希尔排序。

        希尔排序基本思想：将要排序的序列分割成若干个子序列（由相隔这个增量的元素组成），分别进行直接插入排序，然后依次减小增量，从而使整个序列“基本有序”，再对整个序列进行一次直接插入排序。

        这个增量最终必须为1（整体进行直接插入排序），增量序列的长度决定了进行直接插入排序的次数，例如增量序列为5 3 1，就需要进行三次直接插入排序。先按增量为5，分割为若干个子序列，进行一次排序，然后增量为3，进行一次，最后增量为1再进行一次。

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};
int dk[3] = {7,3,1};void shell_insert(int *a,int len,int dk)
{int i,j;//按增量分割为多个子序列//此处并不是显式的对每个子序列进行分别排序，而是逐个遍历，使每个元素都在其子序列中操作//从dk开始是因为直接插入排序都是从第二个元素开始，//因为增量是dk，所以有dk个子序列，每个子序列都跳过第一个元素，所以整体从dk开始for (i = dk; i < len; i++){int tmp = a[i];//进行直接插入排序，注意增量的使用，替代+1和-1for (j = i - dk; j >= 0 && tmp < a[j]; j -= dk){a[j + dk] = a[j];}//在正确位置上插入a[j + dk] = tmp;}
}void shell_sort(int *a,int len,int *dk,int t)
{for (int i = 0; i < t; i++){//对子序列进行多次直接插入排序，次数为增量序列的长度t，每次排序的增量为dkshell_insert(a,len,dk[i]);for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}
}int main(int argc, char const *argv[])
{shell_sort(array,9,dk,3);return 0;
}

         关于增量序列的选取，一般选用增量每次除以2，但是这种方法和直接插入排序相比并没有太大改进，另外一种增量序列{pow(2,k) - 1,pow(2,k-1) - 1,...,7,3,1}，或者是增量每次除以3，可以使时间复杂度降低。

三种排序方法的比较