数据结构 ----- 希尔排序

​
​

​ 希尔排序

活动地址：CSDN21天学习挑战赛

一、直接插入排序

因为希尔排序是建立在直接插入排序之上的，如果没有接触过直接插入排序，学习希尔排序会比较难懂，所以学习希尔排序之前我们先把直接插入排序的概念搞清楚；

1.1 概念

直接插入排序将排序序列分成两个区间，一个已经排序的有序区间和一个待排序的无序区间；
直接插入排序每次将一个待排序区间的元素插入有序区间进行排序；
注：

直接插入排序每趟产生的有序区不一定是全局有序区，也就是说在整个排序结束前，处于有序区的元素可能都不在其最终的位置上；

1.2 排序过程

• 下图中黄色的元素代表处于有序区的元素，绿色代表待排序的无序区的元素；
• 可以看出，直接插入排序的过程是每次取一个未排序的元素插入有序区；
• 在有序区内所有的元素永远都是有序的；
• 未排序的元素插入到合适的位置后再取下一个元素，以此循环直至所有元素都参与了排序；

图 1.1

1.3 代码演示

1.3.1

• 建立一个待排序的数组，再编写一个直接插入排序方法，将数组传入该方法；

图 1.2

1.3.2

• 方法内第一步编写一个循环，因为要将数组内每一个元素进行插入排序故排序总量就是数组的长度，而又因为第一个元素插入有序区时无需做任何排序故可省略这一步，直接从第二个元素开始进行排序；

图 1.3

1.3.3

• 将需要进行排序的元素依次和前面所有的元素进行比较寻找合适的位置；
• 为避免待排序元素的数据丢失，故创建一个辅助变量进行对待排序数据的存储；
• 如果所比较到的元素比待排序的元素更大，就向后移动一个位置，待排序数据也暂时先存入所比较元素的原来位置；
• 如果比较到的元素比待排序元素小就直接结束整个循环，因为前面所有的元素都处于有序状态，如果比较到了比自身小的元素就代表不用再更换位置了；

图 1.4

1.4 代码测试

1. 在外层循环增加一条遍历输出，测试方法功能是否正确；
2. 根据输出我们可以发现每一次插入新元素时都放置到了合适的问题，故此方法编写无误；

图 1.5

1.5 直接插入排序代码分享

public class insort{
    public static void main(String[] args) {
        int[] arr = { 98,64,15,36,49,8,56,41,9,68,4,1 };
        insort(arr);

        for (int e : arr) {
            System.out.print(e + " ");
        }
        System.out.println();
        
    }

    public static void insort( int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 ; j--) {
                if ( arr[j] > arr[j+1] ){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }else {
                    break;
                }
            }
        }
}
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

二、希尔排序

2.1 概念

希尔排序是一种分组插入排序，其思想是创建几个增量让排序序列根据增量进行直接插入排序，使得序列变得相对有序然后再进行一次直接插入排序；
注：

希尔排序的目的是让序列变得相对有序，使最后一次插入排序减少移动元素位置的次数；

2.2 排序过程

• 根据增量组成不同的序列进行排序；
• 在下图中，同样的颜色表示处于同一个序列中；
• 每次对一个增量进行排序后整个序列都会变得相对更加有序；
• 最后将所有元素再进行一次排序即可得到一个有序序列；

图 2.1

2.3 代码演示

2.3.1

• 首先也是先将待排序的数组传入；
• 跟直接插入排序的区别是希尔排序会根据增量的数量进行多次排序，故直接插入排序首先要获得增量的数量；
• 获得增量的数量后确定进行排序的次数，并将每一次的增量读入并将增量和数组传入排序方法；

图 2.2

2.3.2

• 跟直接插入排序的区别在于多了一个循环控制，该循环控制用于确定分组个数，而增量个数就相当于分组个数；
• 要注意的是因为进行了分组，虽然进行的也是直接插入排序，但是所进行的增减操作是跟增量相关的；（例如说增量为 3 ，那么每一组的元素的位置就不是相邻的，而是为 3 ，故不论是遍历下一个元素还是寻找上一个元素都不是 +1、-1，而是 +3、-3）

图 2.3

2.4 代码测试

1. 在每一次调用排序方法后进行遍历输出；
2. 通过控制台得到的结果我们可以得知代码有效；

图 2.4

2.5 希尔排序代码分享

import java.util.Scanner;

public class Shell {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = { 98,64,15,36,49,8,56,41,9,68,4,1 };

        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            System.out.println("第 " + (i+1) + " 次排序，" + "增量为 " + num + " 排序结果为：");
            shell(num,arr);
            for (int j : arr) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
    public static void shell(int n,int[] arr){
        for (int k = 0; k < n; k++) {
            for (int i = k; i < arr.length; i += n) {
                for (int j = i - n; j >= 0 ; j -= n) {
                    if ( arr[j] > arr[j+n] ){
                        int temp = arr[j+n];
                        arr[j+n] = arr[j];
                        arr[j] = temp;
                    }else {
                        break;
                    }
                }

            }
        }
    }
}
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