希尔排序

1.思路

把整个数组先找出中间数mid=（length/2),用mid的个数分成5组，用插入排序，排每一组，再把mid=mid/2,再分成mid组，知道mid==0才停止。

1
for (int i = arr.length/2; i >0; i/=2) {//分组

eE6XLV.md.png

1
2
3
4
5
6
7
8
9
for (int j = i; j <arr.length ; j++) {//选择排序，从mid开始数，找j-i来比较，
                int k=j-i;
                int tem=arr[j];//要插入的元素
                while (k>=0&&tem<arr[k]){
                    arr[k+i]=arr[k];
                    k-=i;
                }
                arr[k+i]=tem;
            }

2完整代码

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
public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr={8,9,1,7,2,3,5,4,6,0};
//        for (int i = arr.length/2; i >0 ; i/=2) {//要分的组数
//            for (int j = i; j <arr.length ; j++) {//从哪里形成组数
//                for (int k = j-i; k>=0 ; k-=i) {//形成组，夸区域
//                    if (arr[k+i]<arr[k]){
//                        int tem=arr[k+i];
//                        arr[k+i]=arr[k];
//                        arr[k]=tem;
//                    }
//                }
//
//            }
//
//        }

        //优化希尔排序，用移位法
        for (int i = arr.length/2; i >0; i/=2) {
            for (int j = i; j <arr.length ; j++) {
                int k=j-i;
                int tem=arr[j];//要插入的元素
                while (k>=0&&tem<arr[k]){
                    arr[k+i]=arr[k];
                    k-=i;
                }
                arr[k+i]=tem;
            }

        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}