1、希尔排序介绍
希尔排序（Shell`s Sort） 是插入排序的一种，也叫作 “缩小增量排序”（Diminishing Increment Sort），由 D.L.Shell 在 1959 年提出，是直接插入排序算法的一种更高效的改进版本，希尔排序是非稳定排序算法
插入排序问题：当插入的数较小，后移的次数明显增多
希尔排序基于插入排序改进的地方
1、 插入排序在对几乎已经排好序的数据进行操作时，效率高，可以达到线性排序的销量；
2、 插入排序一般来说较为低效，因为插入排序每次只能将数据移动一位；
2、希尔排序的思想
选一个数作为第一个增量，把要排序的数据进行分组，对分组后的数据分别进行插入排序，伴随增量减少，每组包含的关键词越来越多，增量减少到 1 时，整个文件被分为一组，算法终止
3、希尔排序代码实现
希尔排序（交换式）算法实现
- 首先是对每次实现步骤的拆解，逐步推导
public static void main(String[] args) {
int[] arr = {
4, 2, 5, 7, 9, 6, 0, 1, 3};
shellSort(arr);
}
public static void shellSort(int[] arr) {
// 初始增量，arr.length/2，数组 arr 被分为 arrLength 组
int arrLength = arr.length / 2;
// 希尔排序第一轮，按照 arrLength 组数据进行
for (int i = arrLength; i < arr.length; i++) {
// 遍历各组中所有的元素
for (int j = i - arrLength; j >= 0; j -= arrLength) {
// 如果当前元素大于加上步长后的元素，进行交换
if (arr[j] > arr[j + arrLength]) {
int temp = arr[j];
arr[j] = arr[j + arrLength];
arr[j + arrLength] = temp;
}
}
}
System.out.println( "第一轮排序后结果：" + Arrays.toString(arr));
// 希尔排序第二轮，重新按照增量进行拆分，拆分后进行插入排序
int arrLength2 = arrLength/2;
for (int i = arrLength2; i < arr.length; i ++) {
for (int j = i - arrLength2; j >= 0; j -= arrLength2) {
if (arr[j] > arr[j + arrLength2]) {
int temp = arr[j];
arr[j] = arr[j + arrLength2];
arr[j + arrLength2] = temp;
}
}
}
System.out.println( "第二轮排序后结果：" + Arrays.toString(arr));
// 希尔排序第三轮
int arrLength3 = arrLength2/2;
for (int i = arrLength3; i < arr.length; i ++) {
for (int j = i - arrLength3; j >= 0; j -= arrLength3) {
if (arr[j] > arr[j + arrLength3]) {
int temp = arr[j];
arr[j] = arr[j + arrLength3];
arr[j + arrLength3] = temp;
}
}
}
System.out.println( "第三轮排序后结果：" + Arrays.toString(arr));
}
- 完整实现
public static void main(String[] args) {
int[] arr = {
4, 2, 5, 7, 9, 6, 0, 1, 3};
shellSort2(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort2(int[] arr) {
// 使用循环进行，逐步减少分组
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历每个分组中的数据，步长为 gap
for (int j = i - gap; j >= 0; j -= gap) {
// 当前元素大于当前下标加上步长后的元素，数据进行交换
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
希尔排序（移位式）代码实现
public static void main(String[] args) {
int[] arr = {
4, 2, 5, 7, 9, 6, 0, 1, 3};
shellSort3(arr);
System.out.println(Arrays.toString(arr));
}
public static void shellSort3(int[] arr) {
// 外层循环依旧是分组循环
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[i];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
// 当前元素移动
arr[j] = arr[j - gap];
j -= gap;
}
// 退出循环，找到插入位置
arr[j] = temp;
}
}
}
}