for (int i = 0; i < numsSize - gap; i++) { int end = i; int temp = nums[end + gap]; while (end >= 0) { if (temp < nums[end]) { nums[end + gap] = nums[end]; end -= gap; } else break; } nums[end + gap] = temp; }
- 最后还要不断缩小gap的值，直到gap == 1
int gap = numsSize; while (gap > 1) { gap /= 2; //不断缩小gap /* 也可以写成 gap = gap / 3 + 1; 总之，必须要保证最后一次gap == 1 */ for (int i = 0; i < numsSize - gap; i++) { int end = i; int temp = nums[end + gap]; while (end >= 0) { if (temp < nums[end]) { nums[end + gap] = nums[end]; end -= gap; } else break; } nums[end + gap] = temp; } }
实现代码
void ShellSort(int* nums, int numsSize) { int gap = numsSize; while (gap > 1) { gap /= 2; for (int i = 0; i < numsSize - gap; i++) { int end = i; int temp = nums[end + gap]; while (end >= 0) { if (temp < nums[end]) { nums[end + gap] = nums[end]; end -= gap; } else break; } nums[end + gap] = temp; } } }
直接插入排序与希尔排序的效率比较
- 看到希尔排序有三层循环，可能有小伙伴会疑惑希尔排序为什么会比直接插入排序快，这里我们先上测试代码，直观的来感受这两个排序算法之间的差距：
测试代码：
#include<stdio.h> #include<stdlib.h> #include<time.h> //直接插入排序 void InsertSort(int* nums, int numsSize) { for (int i = 0; i < numsSize - 1; i++) { int end = i; int temp = nums[end + 1]; while (end >= 0) { if (temp < nums[end]) { nums[end + 1] = nums[end]; end--; } else break; } nums[end + 1] = temp; } } //希尔排序 void ShellSort(int* nums, int numsSize) { int gap = numsSize; while (gap > 1) { gap /= 2; for (int i = 0; i < numsSize - gap; i++) { int end = i; int temp = nums[end + gap]; while (end >= 0) { if (temp < nums[end]) { nums[end + gap] = nums[end]; end -= gap; } else break; } nums[end + gap] = temp; } } } int main() { srand((unsigned int)time(NULL)); //创建两个大小为N的数组 const int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); //为数组赋随机值 for (int i = 0; i < N; i++) { a1[i] = rand(); a2[i] = a1[i]; } /* clock()函数可以记录当前时间 begin和end的差即排序算法运行的时间 注：时间的单位为毫秒(ms) */ int beginl = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); printf("InsertSort:%d\n", end1 - beginl); printf("ShellSort:%d\n", end2 - begin2); //释放内存 free(a1); free(a2); return 0; }
测试结果：
- 我们可以看到，当数据个数为十万个时，直接插入排序所需要的时间是的希尔排序的100多倍
- 当数据个数为一百万个时，直接插入排序所需要的时间时希尔排序的2000倍、
- 可见，数据越多，希尔排序的优势就越明显，节省点时间就越多
时间复杂度
- 从上面的测试中，我们直观的感受到了相较于直接插入排序，希尔排序的优越性，那么具体的希尔排序的时间复杂度为多少呢？
- 我们先来看最外层的循环：
int gap = numsSize; while (gap > 1) { gap /= 2; ………… }
- 设最外层循环运行了x次，那么2x = numsSize，x = log2N，即最外层的时间复杂度为log2N
- 再看里面两层循环：
for (int i = 0; i < numsSize - gap; i++) { int end = i; int temp = nums[end + gap]; while (end >= 0) { if (temp < nums[end]) { nums[end + gap] = nums[end]; end -= gap; } else break; } nums[end + gap] = temp; }
- 当gap很大时，尽管有两层循环，但数据之间跳跃的很大，需要排序的次数很少，因此时间复杂度为O(N)，例如这种情况：
- 当gap很小时，尽管有两层循环，但此时数据已经接近有序，需要排序的次数也很少，因此时间复杂度也为O(N)。
- 综上，希尔排序的时间复杂度为O(NLog2N)
- 也可以认为时间复杂度为O(N1.3)
