希尔排序
思路
1、选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组。
2、对每一个分好组的数据完成排序
3、减少增长量,最小减为1,重复第二步操作。
原始数据
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
9 | 1 | 2 | 5 | 7 | 4 | 8 | 6 | 3 | 5 |
第一次排序
我们选择增长量h为5 (也就是数组的长度/2)
整个数组被分为5组。
每一组进行比较交换
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 1 | 2 | 3 | 5 | 9 | 8 | 6 | 5 | 7 |
第二次排序
我们选择增长量为第一次的一半,h = 5/2 = 2
整个数组被分为2组
每一组进行比较交换
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
2 | 1 | 4 | 3 | 5 | 6 | 5 | 7 | 8 | 9 |
第三次排序
我们选择增长量为第一次的一半,h = 2/2 = 1
整个数组被分为1组
进行比较交换,这次排序后就得到了结果
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 5 | 6 | 7 | 8 | 9 |
第一次排序代码
public class ShellSort {
public static void main(String[] args) {
int[] value = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
new ShellSort().sort(value);
for (int item : value) {
System.out.print(item + ",");
}
}
public void sort(int[] value){
int temp = 0;
for (int i = 5; i < value.length; i++) {
for (int j = i - 5; j >= 0; j -= 5) {
if (value[j] > value[j + 5]) {
temp = value[j];
value[j] = value[j + 5];
value[j + 5] = temp;
}
}
}
}
}
运行结果:4,1,2,3,5,9,8,6,5,7,
第二次排序代码
public class ShellSort {
public static void main(String[] args) {
int[] value = {4,1,2,3,5,9,8,6,5,7};
new ShellSort().sort(value);
for (int item : value) {
System.out.print(item + ",");
}
}
public void sort(int[] value){
int temp = 0;
for (int i = 2; i < value.length; i++) {
for (int j = i - 2; j >= 0; j -= 2) {
if (value[j] > value[j + 2]) {
temp = value[j];
value[j] = value[j + 2];
value[j + 2] = temp;
}
}
}
}
}
运行结果:2,1,4,3,5,6,5,7,8,9,
第三次排序代码
public class ShellSort {
public static void main(String[] args) {
int[] value = {2,1,4,3,5,6,5,7,8,9};
new ShellSort().sort(value);
for (int item : value) {
System.out.print(item + ",");
}
}
public void sort(int[] value){
int temp = 0;
for (int i = 1; i < value.length; i++) {
for (int j = i - 1; j >= 0; j -= 1) {
if (value[j] > value[j + 1]) {
temp = value[j];
value[j] = value[j + 1];
value[j + 1] = temp;
}
}
}
}
}
运行结果:1,2,3,4,5,5,6,7,8,9,
最终代码
我们用外层循环控制增长量h即可
public class ShellSort {
public static void main(String[] args) {
int[] value = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
new ShellSort().sort(value);
for (int item : value) {
System.out.print(item + ",");
}
}
public void sort(int[] value) {
int temp = 0;
for (int h = value.length / 2; h > 0; h = h / 2) {
for (int i = h; i < value.length; i++) {
for (int j = i - h; j >= 0; j -= h) {
if (value[j] > value[j + 1]) {
temp = value[j];
value[j] = value[j + h];
value[j + h] = temp;
}
}
}
}
}
}
运行结果:1,2,3,4,5,5,6,7,8,9,