希尔排序

希尔排序的思想是按照下标的一定增量分组,对魅族使用直接插入排序算法进行排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减少到1时,整个文件恰好被分成一组,算法终止。
简单来说就是按照一定步长分组,例如100个数排序,第一次分50组,每组两个数,第二次分25组,每组4个数,第三次分12组,第四次分6组,第五次分3组,第六次分1组。每一次分组后在组内进行排序。

排序流程:

希尔排序

代码实现:

首先分组,然后使用交换法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void shellSort(int[] arr) {
// 第一个循环,对数组进行分组,直到gap=1为止
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//交替遍历所有组
for (int i = gap; i < arr.length; i++) {
// 组内排序,使用交换法
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
arr[j] = arr[j] ^ arr[j + gap];
arr[j + gap] = arr[j] ^ arr[j + gap];
arr[j] = arr[j] ^ arr[j + gap];
}
}
}
}
}

使用交换法,每次对比都要进行交换,效率比较低,内部排序的方式可以修改成直接插入排序。

分组,然后插入法(希尔排序):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void shellSort2(int[] arr) {
// 第一个循环,对数组进行分组,直到gap=1为止
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 交替遍历所有的组
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;
}
}
}
}

希尔排序是对直接插入排序的更高效的改进版本,