数据结构与算法-希尔排序

什么是希尔排序
希尔排序的名称来源于它的发明者Donald Shell，希尔排序是插入排序算法的一种，是直接插入排序的优化，又称缩小增量排序。

算法原理
希尔排序一般指定2h\3h为步长进行组内元素排序，然后逐渐缩小步长至步长为1。直接插入排序无论元素分布是否均匀都必须对比每个待排序元素后进行插入操作，而希尔排序则增加了步长限制，可以增加比较插入跨度从而缩短算法时间。

时间复杂度
1、最好的情况已有序列，此时的时间复杂度为O(N)
2、最差的情况是完全乱序，此时的时间复杂度为O(N（1.3-2.0）)
综合时间复杂度应该是小于O(N2)

算法稳定性
由于希尔排序会对指定步长依次增加进行元素对比并插入元素，比如 5 5 2 8 9 数组，先指定步长为2，假设为升序第一次排序就会将第一个5元素和2元素进行交换，使得两个5元素索引前后位置改变。故希尔排序算法不稳定。

小试牛刀
1、创建希尔排序升序、降序算法类

/**
 * 希尔排序
 * @author senfel
 * @version 1.0
 * @date 2022/12/6 10:02
 */
@Slf4j
public class ShellSort {


    /**
     * 希尔排序-升序
     * @param array
     * @author senfel
     * @date 2022/12/6 10:05
     * @return void
     */
    public static void sort(int[] array){
        if(null == array || array.length == 1){
           return;
       }
       int length = array.length;
       int num = 0;
       for(int step = length / 2;step > 0;step /= 2){
            num++;
       }
       length = array.length;
       log.error("希尔排序 >> 升序，数据长度为：{},预计排序分组为：{}次。",length,num);
       //我们采用官方推荐的2h为步长，3h及其他步长大同小异
       for(int step = length / 2;step > 0;step /= 2){
           //依次以当前步长依次进行数据比对，比对元素不满足升序规则则进行插入操作
           for(int i = step;i<length;i++){
               //缓存插入位置及待插入数据
               int tempIndex = i;
               int temp = array[tempIndex];
               //保证0号元素对比且不造成数据越界 tempIndex - step >= 0
               //升序判断 array[tempIndex] < array[tempIndex - step]
               /*while (tempIndex - step >= 0 && array[tempIndex] < array[tempIndex - step]){
                   //对比的两个元素不满足升序交换位置
                   array[tempIndex] = array[tempIndex-step];
                   //由于交换位置需要验证上一组元素是否满足升序
                   tempIndex -= step;
                   //交换位置保证当前数组按照指定规则排序
                   array[tempIndex] = temp;
               }*/
               //直接到满足规则的时候插入
               while (tempIndex - step >= 0 && temp < array[tempIndex - step]){
                   //对比的两个元素不满足升序交换位置
                   array[tempIndex] = array[tempIndex-step];
                   //由于交换位置需要验证上一组元素是否满足升序
                   tempIndex -= step;
               }
               //交换位置保证当前数组按照指定规则排序
               array[tempIndex] = temp;

           }
           log.error("步长为：{} 排序完成，数据结构为：{}",step, Arrays.toString(array));
        }
    }

    /**
     * 希尔排序 >> 降序
     * @param array
     * @author senfel
     * @date 2022/12/6 10:47
     * @return void
     */
    public static void invertedSort(int[] array){
        if(null == array || array.length == 1){
            return;
        }
        int length = array.length;
        int num = 0;
        for(int step = length / 2;step > 0;step /= 2){
            num++;
        }
        length = array.length;
        log.error("希尔排序 >> 降序，数据长度为：{},预计排序分组为：{}次。",length,num);
        //我们采用官方推荐的2h为步长，3h及其他步长大同小异
        for(int step = length / 2;step > 0;step /= 2){
            //依次以当前步长依次进行数据比对，比对元素不满足降序规则则进行插入操作
            for(int i = step;i<length;i++){
                //缓存插入位置及待插入数据
                int tempIndex = i;
                int temp = array[tempIndex];
                //保证0号元素对比且不造成数据越界 tempIndex - step >= 0
                //降序判断 array[tempIndex] < array[tempIndex - step]
                /*while (tempIndex - step >= 0 && array[tempIndex] > array[tempIndex - step]){
                    //对比的两个元素不满足降序交换位置
                    array[tempIndex] = array[tempIndex-step];
                    //由于交换位置需要验证上一组元素是否满足降序
                    tempIndex -= step;
                    //交换位置保证当前数组按照指定规则排序
                    array[tempIndex] = temp;
                }*/
                //直接到满足规则的时候插入
                while (tempIndex - step >= 0 && temp > array[tempIndex - step]){
                    //对比的两个元素不满足降序交换位置
                    array[tempIndex] = array[tempIndex-step];
                    //由于交换位置需要验证上一组元素是否满足降序
                    tempIndex -= step;
                }
                //交换位置保证当前数组按照指定规则排序
                array[tempIndex] = temp;

            }
            log.error("步长为：{} 排序完成，数据结构为：{}",step, Arrays.toString(array));
        }
    }
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

2、提供测试方法

public static void main(String[] args) {
    int[] array = {5,5,2,6,1,7,9,8,1};
    sort(array);
    int[] array2 = {5,5,2,6,1,7,9,8,1};
    invertedSort(array2);

}
1
2
3
4
5
6
7

3、运行测试方法并查看每个步长执行后的结果

10:56:58.041 希尔排序 >> 升序，数据长度为：9,预计排序分组为：3次。
10:56:58.044 步长为：4 排序完成，数据结构为：[1, 5, 2, 6, 1, 7, 9, 8, 5]
10:56:58.044 步长为：2 排序完成，数据结构为：[1, 5, 1, 6, 2, 7, 5, 8, 9]
10:56:58.044 步长为：1 排序完成，数据结构为：[1, 1, 2, 5, 5, 6, 7, 8, 9]

10:56:58.044 希尔排序 >> 降序，数据长度为：9,预计排序分组为：3次。
10:56:58.044 步长为：4 排序完成，数据结构为：[5, 7, 9, 8, 1, 5, 2, 6, 1]
10:56:58.044 步长为：2 排序完成，数据结构为：[9, 8, 5, 7, 2, 6, 1, 5, 1]
10:56:58.044 步长为：1 排序完成，数据结构为：[9, 8, 7, 6, 5, 5, 2, 1, 1]