释放双眼，带上耳机，听听看~！
希尔排序介绍
希尔排序，也称递减增量排序算法（缩小增量排序），是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法
希尔排序基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件被分成一组，算法便终止
希尔排序算法讲解（需要有直接插入排序算法作为基础知识）
（说明：分组个数等于下标增量等于步长，说的都是同一个意思，分组=下标增量=步长）
以数组 {82 ,31 ,29 ,71, 72, 42, 64, 5, 110} 为例
该数组长度为9，初始增量初始默认设置为数组长度的一半，取整，为4
就可以把以上数组分为以下四个子数组，然后对每个子数组分别进行直接插入排序
子数组1
子数组2
子数组3
子数组4
对每个子数组进行直接插入排序后得到以下数组：
重新设置增量 = 之前增量的1/2 即是4/2=2
在增量为2的前提下，分成以下两个子数组，分别对各个子数组进行直接插入排序
子数组1
子数组2
对每个子数组进行直接插入排序后得到以下数组：
重新设置增量 = 之前增量的1/2 即是2/2=1
增量为1的时候，就是对整个数组分成一组，进行直接插入排序
得到最终排序结果：
代码实现
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
2
3import java.util.Arrays;
4
5/**
6 * @Auther: Administrator
7 * @Date: 2020/3/8 14:36
8 * @Description: 希尔排序（直接插入排序的升级版）
9 */
10public class ShellSort {
11 public static void main(String[] args) {
12 int[] array = {82, 31, 29, 71, 72, 42, 64, 5, 110};
13
14 shellSort(array);
15 System.out.println(Arrays.toString(array));
16 /*[5, 29, 31, 42, 64, 71, 72, 82, 110]*/
17 }
18
19 /**
20 * 希尔排序算法
21 * @param array 待排序数组
22 *
23 * 说明：分组个数即为步长，或者即为下表增量
24 */
25 private static void shellSort(int[] array) {
26 //待插入元素
27 int insertValue;
28 // 初始默认值为各个分组每次循环比较开始时，待插入元素左边的已排序元素的索引位置
29 int insertIndex;
30 // 对待排序数组进行分组
31 // 初始分组个数为数组长度的一半
32 // gap /= 2 分组逐步减半，向1靠近
33 for(int gap = array.length / 2; gap > 0; gap /= 2) {
34 // 对各个分组中的若干元素进行直接插入排序
35 // 共有gap个分组
36 for(int i = 0; i < gap; i++) {
37 // 取出各个分组中的元素进行直接插入排序
38 // j = gap + i 默认每一个分组中的第一个元素为已排序，需要找出下一个元素与已排序元素进行比较排序
39 // j < array.length 能够获取到每一个分组中的全部元素
40 // j += gap 元素下标差等于步长gap的元素都在同一个分组中
41 for(int j = gap + i; j < array.length; j += gap) {
42 // 如果待插入元素比已排序元素小，则需要比较找出插入位置
43 if(array[j] < array[j - gap]) {
44 //待插入元素
45 insertValue = array[j];
46 // 初始默认值为各个分组每次循环比较开始时，待插入元素左边的已排序元素的索引位置
47 insertIndex = j - gap;
48 // insertIndex >= 0 保证在给待插入元素insertVal找插入位置，数组下标不越界
49 // insertVal < arr[insertIndex] 待插入元素还没有找到要插入的位置
50 while(insertIndex >= 0 && insertValue < array[insertIndex]) {
51 // 如果待插入元素小于已排序元素，则将已排序元素向后移动一个位置
52 array[insertIndex + gap] = array[insertIndex];
53 // 继续与已排序元素进行比较
54 insertIndex -= gap;
55 }
56 // 退出while循环，待插入元素已找到插入位置，为insertIndex + gap
57 array[insertIndex + gap] = insertValue;
58 }
59 }
60 }
61 }
62 }
63}
64
65
