“希尔”排序

大家好，欢迎来到IT知识分享网。

一、什么是希尔排序？

二、如何实现希尔排序？

代码如下：

void InsertSort(int* a, int n) { 
    int end = 0; int tmp = 0; int i = 0; for (i = 0; i < n - 1; i++) { 
    end = i ;//end位置为i tmp = a[end + 1];//则需要插入的数的位置为end+1，即end的后一个 //tmp这个待插入的数与从end开始往前直到0的数比较，直到找到比tmp小的数就break； while (end >= 0) { 
    if (tmp < a[end]) { 
    a[end + 1] = a[end]; --end; } else { 
    break; } } //来到这里无论是break跳出循环还是while循环结束跳出循环，tmp都是 // 放在end+1的位置上，while循环结束跳出的话就是把tmp插入到第一个 // 位置，break跳出是插入到中间位置或者最后一个位置 a[end + 1] = tmp; } } void ShellSort1(int* a, int n) { 
    //首先可以把gap初始化为3，但不一定是3，可以自己选一个适当的数定义gap， //gap是几就说明距离为gap的数分到同一组内，进行分组预排序 int gap = 3; int i = 0; int end = 0; int tmp = 0; int j = 0; //以gap为距离的每一组数都要进行排序 //一定是gap组数，只是它们不一定是平均的(每组有n/gap个数，一共必定是gap组) for (j = 0; j < gap; j++) { 
    //i+=gap刚好就是对距离为gap的一组元素进行预排序， // 这里跑一次循环就是对一组间隔为gap的数进行了 // 一次直接插入排序，那这一组数就变成了有序的了， // 预排序是为了使整个数组更接近有序。 // 其实把这里的gap初始化为1就是一次直接插入排序。 // 所以可以对照着直接插入排序来理解这里的。 //这里的i需要小于n-gap，具体说明看上图 for (i = j; i < n - gap; i += gap) { 
    end = i; tmp = a[end + gap]; while (end >= 0) { 
    //往前找>=tmp的数 //如果tmp比前一个数小，那就挪动数据(这里的“一”是以gap为单位的) //再往前找，直到找到或者循环结束为止 if (tmp < a[end]) { 
    a[end + gap] = a[end]; end -= gap; } //如果找到了就break了 else { 
    break; } } //来到这里无论是while循环结束还是中途break出来都 //是把tmp放到a[end+gap]的位置，while循环结束跳出 //证明这里是头插而已 a[end + gap] = tmp; } } //最后必须进行一次gap=1的直接插入排序才能使数组有序 //经过了前面的预排序，整个数组已经更接近于 //有序的了，所以直接插入排序的效率会很高 InsertSort(a, n); } 

以上代码的两个循环也可以转化成一个循环，就是gap组的数按下标顺序进行插入排序：先对黑色组的第二个数进行插入排序(相对于黑色组内的数插入)，然后不直接对黑色组的第三个数插入，而是对红色组的第二个数进行插入排序(相对于红色组内的数插入)，然后再对蓝色组的第二个数进行插入排序(相对于蓝色组内的数插入)，下一次才又回到黑色组的第三个数进行插入排序，以此类推，就能完成gap组数的预排序了。

代码如下：

void ShellSort2(int* a, int n) { 
    int gap = 3; int i = 0; int end = 0; int tmp = 0; //这里变成i++，gap组数同时进行插入排序，其它都跟上面的没有变化 for (i = 0; i < n - gap; i ++ ) { 
    end = i; tmp = a[end + gap]; //走一趟就把一个数插入到自己分组内适当的位置 while (end >= 0) { 
    if (tmp < a[end]) { 
    a[end + gap] = a[end]; end -= gap; } else { 
    break; } } a[end + gap] = tmp; } InsertSort(a, n); } 

所以下面这个经过对gap进行动态变化的，实现过多次预排序的才是真正的希尔排序。

代码如下：

void ShellSort3(int* a, int n) { 
    int gap = n; int i = 0; int end = 0; int tmp = 0; while (gap > 1) { 
    gap /= 2; //gap = gap / 3 + 1; for (i = 0; i < n - gap; i++) { 
    end = i; tmp = a[end + gap]; while (end >= 0) { 
    if (tmp < a[end]) { 
    a[end + gap] = a[end]; end -= gap; } else { 
    break; } } a[end + gap] = tmp; } } } 

三、希尔排序的时间复杂度是多少？

以上就是著名的希尔排序，你学会了吗？如果感觉到有所帮助的话，请动动你的小手，点个小心心呗，顺便点个关注，后面会持续更新其它排序方法哦！！！