1 /**
 2      * 希爾排序，選擇一個間隔，然后進行比較交換
 3      */
 4     public static void sort(int[] arr) {
 5         //初始化一個間隔
 6         int interval = 1;
 7         System.out.println("arr.length/3 = " + arr.length/3);
 8         //計算最大間隔
 9         while (interval < arr.length / 3) {
10             interval = interval * 3 + 1;
11         }
12         System.out.println("間隔 = " + interval);
13         int n = 0;
14         while(interval > 0) {
15             //進行插入排序
16             int tmp = 0;
17             for (int i = interval; i < arr.length; i++) {
18                 tmp = arr[i];
19                 int j = i;
20                 while (j > interval - 1 && arr[j - interval] >= tmp) {
21                     arr[j] = arr[j - interval];
22                     j -= interval;
23                     n++;
24                 }
25                 arr[j] = tmp;
26             }
27             //減少間隔
28             interval = (interval - 1) / 3;
29         }
30         System.out.println("循環次數：" + n);
31     }
32 
33     @Test
34     public void shellSort(){
35         int[] arr = new int[15];
36         for (int i = 0; i < arr.length; i++) {
37             arr[i] = (int) (Math.random()*100);
38         }
39         System.out.println("------原始數據------\n"+
40                 Arrays.toString(arr));
41         sort(arr);
42         System.out.println("------排序結果-------");
43         System.out.println(Arrays.toString(arr));
44     }