forked from wujun728/jun_java_plugin
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathShellSort.java
More file actions
104 lines (94 loc) · 2.69 KB
/
ShellSort.java
File metadata and controls
104 lines (94 loc) · 2.69 KB
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package sort;
/**
* 希尔排序
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩
小增量排序，因 DL．Shell 于 1959 年提出而得名。
希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
算法描述：
先取一个正整数 d1<n，把所有序号相隔 d1 的数组元素放一组，组内进行直接插入排
序；然后取 d2<d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中
排序为止 。
过程举例：
假设待排序文件有 10 个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列 d 的取值依次为：
5，3，1
d=5
49 38 65 97 76 13 27 49* 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49*
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟结果
13 27 49* 55 04 49 38 65 97 76
--------------------------------------------------------------------
d=3
13 27 49* 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49* 49 97
|------------|------------|
二趟结果
13 04 49* 38 27 49 55 65 97 76
---------------------------------------------------------------------
d=1
13 04 49* 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟结果
04 13 27 38 49* 49 55 65 76 97
---------------------------------------------------------------------
* @author <a href="mailto:ketayao@gmail.com">ketayao</a>
* @since 2014年1月23日 下午4:56:56
*/
public class ShellSort extends Sort {
/**
* @param args
*/
public static void main(String[] args) {
new ShellSort().sort(array);
}
/* (non-Javadoc)
* @see sort.Sort#execute(int[])
*/
@Override
public void execute(int[] array) {
// int i,j,k;
// int t;
//
// k = array.length / 2;
// System.out.println(k + "--");
// while (k > 0) {
// for (i = k; i < array.length; i++) {
// t = array[i];
// for (j = i - k; j >= 0 && array[j] > t; j -= k)
// array[j + k] = array[j];
// array[j + k] = t;
// }
// k /= 2;
// System.out.println(k + "--");
// print(array);
// }
int d = array.length / 2;
while (d > 0) {
System.out.println(d + "--");
for (int i = d; i < array.length; i++) {
int t = array[i];
int j;
for (j = i - d; j >= 0 && array[j] > t; j -= d) {
array[j + d] = array[j];
}
array[j + d] = t;
}
print(array);
d /= 2;
}
}
}