package com.atguigu.sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
System.out.println("排序前" + Arrays.toString(arr));
shellSort(arr);
System.out.println("交换式排序后" + Arrays.toString(arr));
shellSort2(arr);
System.out.println("移位排序后" + Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
//希尔排序时,对有序序列插入时采用交换法
int temp;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {//分成了gap组,i从gap开始是为了方便内层的for循环
//这里从gap到arr.length的循环非常巧妙,避免了数组引用出界
//遍历每一组的元素
for (int j = i - gap; j >= 0; j -= gap) {//相当于每一组中从后向前遍历
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
//方式一:正确
// //希尔排序的第一轮:其中5是组数
// int temp;
// for (int i = 5; i < arr.length; i++) {//分成了5组,i从5开始是为了方便内层的for循环
// //遍历每一组的元素
// for (int j = i - 5; j >= 0; j -= 5) {//相当于每一组中从后向前遍历
// if (arr[j] > arr[j + 5]) {//此时的arr[j]是同一组中的最后一个元素
// temp = arr[j];
// arr[j] = arr[j + 5];
// arr[j + 5] = temp;
// }
//
// }
// }
// System.out.println("第一轮排序后" + Arrays.toString(arr));
//
// for (int i = 2; i < arr.length; i++) {
// //遍历每一组的元素
// for (int j = i - 2; j >= 0; j -= 2 ){//相当于每一组中从后向前遍历
// if (arr[j] > arr[j + 2]) {//此时内部组的排序相当于是小冒泡
// temp = arr[j];
// arr[j] = arr[j + 2];
// arr[j + 2] = temp;
// }
//
// }
// }
// System.out.println("第二轮排序后" + Arrays.toString(arr));
// //方式2:错误
// 第一轮还可以,但是后边第二轮开始就无法对一组的数进行排序。
// int temp;
// for (int i = 0; i < arr.length-5; i++) {
// for (int j = i; j + 5 < arr.length; j += 5) {
// if (arr[j] > arr[j + 5]) {
// temp = arr[j];
// arr[j] = arr[j + 5];
// arr[j + 5] = temp;
// }
// }
// }
// System.out.println("希尔排序一轮后" + Arrays.toString(arr));
//
// for (int i = 0; i < arr.length-5; i++) {
// for (int j = i; j + 2 < arr.length; j += 2) {
// if (arr[j] > arr[j + 2]) {
// temp = arr[j];
// arr[j] = arr[j + 2];
// arr[j + 2] = temp;
// }
// }
// }
// System.out.println("希尔排序二轮后" + Arrays.toString(arr));
}
//对交换式希尔排序进行优化->移位法
public static void shellSort2(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第gap个元素,逐个对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int insertIndex = i;
int insertVal = arr[insertIndex];
while (insertIndex - gap >= 0 && insertVal < arr[insertIndex - gap]) {
arr[insertIndex] = arr[insertIndex-gap];
insertIndex-=gap;
}
//当退出while循环后就给insertVal找到了插入的位置
arr[insertIndex]=insertVal;
}
}
}
}
希尔排序其实就是对插入排序加入了gap分组的条件,分不同的组进行插入排序。



