-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathShellSort.java
More file actions
50 lines (42 loc) · 1.49 KB
/
ShellSort.java
File metadata and controls
50 lines (42 loc) · 1.49 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
package com.liang.algorithm;
import java.util.Arrays;
/**
* @ClassName ShellSort
* @description 希尔排序
* @Author LiaNg
* @Date 2019-05-28
*/
public class ShellSort {
public static void main(String[] args) {
int[] numbers = {3, 5, 4, 1, 2, 6, 3, 5, 4, 1, 2, 6};
ShellSort shellSort = new ShellSort();
shellSort.shellSort(numbers);
}
public void shellSort(int[] arr) {
if (arr == null) {
return;
}
// 数组的长度
int len = arr.length;
// 初始的增量为数组长度的一半
int k = len / 2;
// while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
// 增量的最小值为1，即最后一次对整个数组做直接插入排序
while (k > 0) {
// 里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
// 所以直接将直接插入排序中的‘1’变为‘k’就可以了。
for (int i = k; i < len; i++) {
int j = i;
int target = arr[i];
while (j >= k && target < arr[j - k]) {
arr[j] = arr[j - k];
j -= k;
}
arr[j] = target;
}
// 不同增量排序后的结果
System.out.println("增量为" + k + "排序之后：" + Arrays.toString(arr));
k /= 2;
}
}
}