Java基础知识强化58：经典算法之希尔排序（ShellSort）

 1 package cn.itcast;
 2 
 3 /*
 4  * 希尔排序：先取一个小于n的整数d1作为第一个增量，
 5  * 把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。
 6  * 先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，
 7  * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 
 8  */
 9 public class ShellSort {
10     public static void sort(int[] data) {
11         for (int i = data.length / 2; i > 2; i /= 2) {
12             for (int j = 0; j < i; j++) {
13                 insertSort(data, j, i);
14             }
15         }
16         insertSort(data, 0, 1);
17     }
18 
19     /**
20      * @param data
21      * @param j
22      * @param i
23      */
24     private static void insertSort(int[] data, int start, int inc) {
25         for (int i = start + inc; i < data.length; i += inc) {
26             for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
27                 swap(data, j, j - inc);
28             }
29         }
30     }
31     /*
32      * 交换数组中的两个元素
33      */
34     public static void swap(int[] data, int i, int j) {
35         int temp = data[i];
36         data[i] = data[j];
37         data[j] = temp;
38     }
39 }
40 /*
41  * 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序 　　 
42  * 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，
43  * 组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1， 即所有记录放进一个组中排序为止 　　 
44  * 初始：d=5 　　49 38 65 97 76 13 27 49 55 04 　　 
45  * 49 13 　　|-------------------| 　　 
46  * 38 27     |-------------------| 　　 
47  * 65 49 　　|-------------------| 　　 
48  * 97 55     |-------------------| 　　 
49  * 76 04 　　|-------------------| 　　 
50  * 一趟结果 　　13 27 49 55 04 49 38 65 97 76 　　 
51  * d=3 　　 13 27 49  55 04 49 38 65 97 76 　　 
52  * 13 55 38 76 |------------|------------|------------| 　　 
53  * 27 04 65 |------------|------------| 　　 
54  * 49 49 97 |------------|------------| 　　
55  * 二趟结果  13 04 49* 38 27 49 55 65 97 76 　　 
56  * d=1 　　13 04 49 38 27 49 55 65 97 76
57  * 　　 |----|----|----|----|----|----|----|----|----| 　　 三趟结果 　　
58  * 04 13 27 38 49 49 55 65 76 97
59  */