【排序】3.希尔排序法

---

希尔排序（直接插入排序的优化）

1.分组思想

上图中gap为5，说明要分成5组。
这5组分别用了五种颜色的线条连接起来了。

第1组：9、4
第2组：1、8
第3组：2、6
第4组：5、3
第5组：7、5

2.缩小增量的过程

前面gap为5的情况排序后会变成下面情况

按照gap把数据分成了两组。

当数据很大的时候，数据的间隔很大。
小的数据会往前方，大的数据会往后放。

gap会逐渐缩小，间隔也会逐渐缩小。

整体的数据会更加趋于有序，这个时候使用直接插入排序效率会更高。

gap为2的时候会排序成下面情况

此时分为了1组，再排序一次后变成下面情况

此时的数据即为有序的。

3.排序情况分析

3.1 排序五组数据的情况

1. gap为5，将数据分为5组，图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据，定义一个 j 变量指向 i - gap 的位置。

2. 将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
   若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
   
   执行后：
   

3. j 变量向 j - gap 位置走，若这个位置的下标为负数。
   则要将 tmp 的值放到 j + gap的位置。
   
   j 变量此时在-5下标处，要将 tmp 的值放到 j + 5的位置。
   
   这一组数据此时为有序了。
   排序下一组数据，i++即可，j 变量依然是在 i - gap 的位置。
   后面4组数据类似，不在演示。
   最终排序结果是：
   

3.2 排序两组数据的情况

1. 此时 gap 为2，数据此时分为了两组。第一组由红色线画出（4、2、5、8、5），第二组由蓝色线画出（1、3、9、6、7）。
   i 变量指向这一组的第二个数据， j 变量指向 i - gap 的位置。
   
2. 将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
   若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
   
   执行后：
   
3. j 变量向 j - gap 位置走，若这个位置的下标为负数。
   则要将 tmp 的值放到 j + gap的位置。
   
   j 变量此时在-2下标处，要将 tmp 的值放到 j + 2的位置。
   
   这一组数据中的 2 和 4 此时为有序了。
   排序下一组数据，i++ 即可，j 变量依然是在 i - gap 的位置。
   后面剩下的数据类似，不在演示。
   最终排序结果是：
   

3.3 排序一组数据的情况

1. i 变量指向第二个数据， j 变量指向 i - gap 的位置。
   
2. 将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
   若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
   
   执行后：
   
3. j 变量向 j - gap 位置走，若这个位置的下标为负数。
   则要将 tmp 的值放到 j + gap的位置。
   
   j 变量此时在-1下标处，要将 tmp 的值放到 j + 1的位置。
   
   此时 前两个数据有序了，后面的数据排序过程类似。
   排序下一组数据，i++ 即可，j 变量依然是在 i - gap 的位置。
   最终结果是：
   

4.代码分析以及实现

1.间隔分组，通常为总长度的一半
2.组内排序
3.重新设置间隔分组，为前一组的一半
4.当gap= 1时,为直接插入排序。

void ShellSort(int *arr, int n)
{// 初始化间隔为数组的长度int gap = n;      while (gap > 1){// 逐渐减小间隔，每次将间隔除以2gap /= 2;// 也可以使用这种方式来减小间隔，这是一种不同的策略// gap = gap / 3 + 1;// 遍历数组，每次跳过gap个元素，对每个子序列进行插入排序for (int i = 0; i < n - gap; i++){// 初始化j为当前元素的索引int j = i;// 保存当前子序列的元素，以便在排序过程中移动int tmp = arr[i + gap];// 将tmp插入到已排序的子序列中的正确位置while (j >= 0){// 如果tmp小于子序列中的元素，则将该元素向后移动一个间隔if (tmp < arr[j]){arr[j + gap] = arr[j];// 继续向前比较j -= gap;}else{// 如果tmp不小于子序列中的元素，则跳出循环break;        }}// 当j为负数时，表示tmp已经找到了正确的位置，将其插入到子序列中arr[j + gap] = tmp;}}
}

执行结果：

5.性能分析