手撕常用排序算法——希尔排序（C语言实现）

手撕常用排序算法——希尔排序（C语言实现）
1、希尔排序思想： 希尔排序本质上也是直接插入排序，但是会先进行预排序，使原序列更接近有序序列，最后将预排之后的序列进行直接插入排序。 2、思路详解： 大家看这个序列：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次。 由此可见，对于一个已经比较有序的序列，采用直接插入排序，效果是非常显著的。那么，我们能不能对序列arr2进行处理后使之变成一个相对有序的序列呢？答案是肯定的，这里我们便用到希尔排序的预排序了。
什么是预排？ 将无序序列以gap为间隔进行分组，所有间隔相同的为一组，分别对每组进行直接插入排序。 如上图：我们假设gap=3，那么我们可

手撕常用排序算法——希尔排序（C语言实现）最先出现在Python成神之路。