【实现常见排序算法】希尔排序的算法思想

一、前言

上一篇文章我们分析了直接插入排序的时间复杂度，已知它在平衡条件时的时间复杂度都接近O(N^2)，为了简化，我们开始寻找方法：

将数组分成多个小数组，分别让他们按照从小到大进行插入排序会不会是一个可行方案，希尔排序则是在此基础上发展来的排序算法。

二、算法思想：

希尔排序又称作缩小增量法，基本思想是先选定一个整数（通常记为gap=n/3 +1），此处n为数组中数据个数，把待排序数组所有数组分成各组，所有距离相等的数据分在同一组内，并对每一组内数据进行插入排序，当gap=1时，就相当于直接插入排序。

gap一般是除以2/3，以n等于6为例，

• 除以2时，gap=3、1、0.
• 除以3时，gap=2、0，可见除以3，可以少一些循环.
• 最后gap要+1，原因是前面已经分组简化了数组，假设gap=0，则最后未进行gap=1时的直接插入排序，故最后gap要+1.

当gap > 1时都是预排序，目的是让数组更接近于有序。

当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

三、代码实现：

void ShellSort(int* arr, int n) { int gap = n; while (gap > 1) { //此处gap必须 > 1 gap = gap/ 3 + 1; //以6为例，gap=3、2、1…最后对gap==1，进行直接插入排序，如若条件为gap>=1，那么就会进入死循环 for (int i = 0;i < n - gap;i++)//注意此处的循环条件， { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end+gap] = tmp; } } }

四、时间复杂度：

希尔排序时间复杂度不好计算，因为gap的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。

// 测试排序的性能对⽐ void TestOP() { srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); /*SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock();*/ int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); /*printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6);*/ printf("BubbleSort:%d\n", end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); }

（单位为毫秒）

内层循环：

//加油加油！