手撕常用排序算法|希尔排序——C语言实现 c语言|数据结构|排序算法

【手撕常用排序算法|希尔排序——C语言实现】
一、希尔排序思想：

希尔排序本质上也是直接插入排序，但是会先进行预排序，使原序列更接近有序序列，最后将预排之后的序列进行直接插入排序。

二、思路详解：

大家看这个序列：arr1[] = {9，8，7，6，5，4，3，2，1，0}，如果用直接插入排序，那么需要往后移动元素的次数为n*(n-1)/2，也就是45次；
但如果是这个序列呢：arr2[] = {0，1，2，3，5，4，8，7，6，9}；，用直接插入排序，需要移动元素的次数仅为4次。

??由此可见，对于一个已经比较有序的序列，采用直接插入排序，效果是非常显著的。那么，我们能不能对序列arr1进行处理后使之变成一个相对有序的序列呢？答案是肯定的，这里我们便用到希尔排序的预排序了。
什么是预排？

预排序：将无序序列以gap为间隔进行分组，所有间隔相同的为一组，分别对每组进行直接插入排序。

文章图片

??如上图：我们假设gap=3，那么我们可以将上面的序列分为红黄蓝三组，对每组进行一次直接插入排序，那么我们将可以得到一个相对有序的序列，
??arr3[]={3,2,1,6,5,4,9,8,7}，这样我们就把大的数尽快的排到序列尾部，小的数尽快的排到序列头部。排一趟就行了吗？接下来直接进行直接插入排序吗？答案否定的。看下图：

文章图片

可以看到，我们会进行多次的预排序，只要gap>1就是预排，当gap==1时，就是直接插入排序。那么我们的代码该怎么写呢？

三、代码实现

//希尔排序 void ShellSort(int* arr, int sz) { int count=0; //这是我为了看看希尔排序和直接插入排序的性能比较而设置的计数 int gap = sz; //设置排序的间隔 while ( gap > 1 ) { //这里一定要保证gap最后进来循环后为1，所以对此加1 gap = gap / 3 + 1; //gap>1为与排序，gap==1，为直接插入排序for (int i = 0; i < sz - gap; i++)//这里并不是一次性把一组排完，而是挨个往后，一组一个轮流排 { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (tmp < arr[end]) { arr[end + gap] = arr[end]; end -= gap; count++; } else { break; } } arr[end + gap] = tmp; } } printf("希尔插入排序后移次数count=%d", count); }void test() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[1]); ShellSort(arr, sz); printf("\n"); Print(arr, sz); }int main() { test(); return 0; }

所有的接口都已经写好，大家可以直接复制到vs2017测试。