希尔排序

分析

  • 先将数组分为length/2组，然后依次/2分组
  • 每组进行插入排序
  • 最后再进行总的插入排序

162002842082

代码

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
package 算法;

public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void shellSort(int[] arr){
        int len = arr.length;
        //循环进行分组，i表示分组数
        for (int i = len/2; i >0 ; i/=2) {
            //开始插入排序
          	//因为分了组所以只遍历len-i次
            for (int j = i; j < len; j++) {
              	//从k位开始遍历比较
                for (int k = j-i; k >=0 ; k-=i) {
                    if(arr[k]>arr[k+i]){
                        int temp = arr[k];
                        arr[k] = arr[k+i];
                        arr[k+i] = temp;
                    }
                }
            }
        }
    }
}

优化：

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
package 算法;

public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void shellSort(int[] arr){
        int len = arr.length;
        //循环进行分组，i表示分组数
        for (int i = len/2; i >0 ; i/=2) {
            //开始插入排序
          	//因为分了组所以只遍历len-i次
            for (int j = i; j < len; j++) {
              int index = j;
              int temp = arr[index];
              for (int k = j-i; k >=0 ; k-=i) {
                    if(temp<arr[k]){
                        arr[index]=arr[k];
                      	index = k;
                    }
                }
              arr[index] = temp;
            }
        }
    }
}