/
Code_03_ShellSort.java
99 lines (92 loc) · 3.07 KB
/
Code_03_ShellSort.java
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
package com.nateshao.basic_01_ten_sort;
import java.util.Arrays;
/**
* @date Created by 邵桐杰 on 2021/10/30 10:44
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: 希尔排序
*/
public class Code_03_ShellSort {
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
shellSort(arr);
System.out.println(Arrays.toString(arr));
shellSort1(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序 针对有序序列在插入时采用交换法
*
* @param arr
*/
public static void shellSort(int[] arr) {
if (arr == null && arr.length < 2) {
return;
}
//增量gap,并逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第gap个元素,逐个对其所在组进行直接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
while (j - gap >= 0 && arr[j] < arr[j - gap]) {
//插入排序采用交换法
swap(arr, j, j - gap);
j -= gap;
}
}
}
}
/**
* 希尔排序 针对有序序列在插入时采用移动法。
*
* @param arr
*/
public static void shellSort1(int[] arr) {
if (arr == null && arr.length < 2) {
return;
}
//增量gap,并逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第gap个元素,逐个对其所在组进行直接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动法
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
public static void swap(int[] arr, int a, int b) {
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
// public static void shellSort(int[] arr) {
// int interval = arr.length / 2; // 默认间隔
//
// while (interval >= 1) {
// for (int i = interval; i < arr.length - 1; i++) {
// int preIndex = i - interval;
// int temp = arr[i];
//
// if (temp < arr[preIndex]) {
// while (preIndex >= 0 && temp < arr[preIndex]) {
// arr[preIndex + interval] = arr[preIndex];
// preIndex -= interval;
// }
// arr[preIndex + interval] = temp;
// }
// }
// interval = interval / 2; // 缩小间隔
// }
// }
}