Java 希尔排序算法
简介
上一章我们学习了 [Java 插入排序算法](https://blog.csdn.net/u011546655/article/details/110930559)，这一章，我们来学习插入排序算法，so，多了不说，继续老规矩，学习内容如下：
1、希尔排序的定义
2、希尔排序的思路
3、代码实现
1.希尔排序的定义
> 希尔排序的实质就是：分组插入排序，它是简单插入排序经过改进之后的一个更高效的版本，又称**缩小增量法**。
>
> 将整个无序序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。
>
> 因为直接插入排序在元素基本有序的情况下，效率是很高的， **因此希尔排序在时间效率上有很大提高**。
2.希尔排序的思路
简单的插入排序
- 默认从第2个数据开始比较。如果第2个数据比第1个小，则交换。
- 然后在用第3个数据比较，如果比前面小，则插入。否则，退出循环。
- 说明：默认将第1数据看成有序列表，后面无序的列表循环每一个数据，如果比前面的数据小则插入（交换）。否则退出。
希尔排序
- 基本上和插入排序一样的道理
- 不一样的地方在于，每次循环的步长，通过减半的方式来实现
- 说明：基本原理和插入排序类似，不一样的地方在于。通过间隔多个数据来进行插入排序。
3.代码实现
```
package com.gongchao.boss;
/**
* description: 希尔排序
* auth: zengtao
* time: 2020-12-11 15:45
**/
public class Main {
public static void main(String[] args) {
int arr[] = {9, 5, 2, 7, 4};
// 希尔排序
sortHill(arr);
}
private static void sortHill(int[] arr) {
// 希尔排序
for (int i = arr.length / 2; i > 0; i /= 2) {
// i层循环控制步长
for (int j = i; j < arr.length; j++) {
// j控制无序端的起始位置
for (int k = j; k > 0 && k - i >= 0; k -= i) {
if (arr[k] < arr[k - i]) {
int temp = arr[k - i];
arr[k - i] = arr[k];
arr[k] = temp;
} else {
break;
}
// 打印排序后的数据
systemArr(arr);
}
}
// j,k为插入排序，不过步长为i
}
}
private static void systemArr(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println("");
}
}
```
运行结果
而一般的插入排序运行结果如下
两者对比：**希尔排序，时间上很明显高效了很多** 实际情况也证明了，希尔排序是高效的，大大的节约了时间
---------------------------------------------------------------------------
我也查阅了很多资料和文献，有这么一个说法
PS：**当需要插入的数是较小的数时，后移的次数明显增多，对效率会有影响**
我这边也测试了下
测试数据 { 2,3,4,5,6,1}
运行结果
同样5个数据的情况下，链路和步的确有所拉长，也可能数据太少，不够明显，但是这个说法的确是正确的。
好了
到此为止，希尔排序已经总结完毕。
***欢迎观看，Thanks ！***