希尔排序：
简单插入排序存在的问题：
我们看简单的插入排序可能存在的问题
数组 arr = {2, 3, 4, 5, 6, 1} 这时需插入的数1(最小)，这样的过程是：
{2, 3, 4, 5, 6, 6}
{2, 3, 4, 5, 5, 6}
{2, 3, 4, 4, 5, 6}
{2, 3, 3, 4, 5, 6}
{2, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5, 6}
结论：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
希尔排序介绍：
希尔排序是希尔(DonaldShell)于1995年提出的一种排序算法。希尔排序也是一种插入排序，它
是简单插入排序经过改进后一个高效版本，也称为缩小增量排序。
希尔排序法基本思想：
希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐
减少，每组包含的关键字越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
希尔排序图解：
希尔排序总结：
经过上面的"分组插入排序"，整个数组的实现了基本的有序化。
此时仅仅需要对以上数组简单微调，无需大量移动操作即可完成整个数组的排序
希尔排序应用实例：
有一群牛，考试成绩分别为{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}，请从小到大排序，请分别使用
1)希尔排序时，对有序序列在插入时采用交换法，并测试排序速度
2)希尔排序时，对有序序列在插入时采用移动法，并测试排序速度
希尔排序(交换法)笨代码如下：推导代码
package sort2;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shellSort(arr);
}
// 使用逐步推导的方式编写希尔排序
public static void shellSort(int[] arr) {
int temp = 0;
// 希尔排序的第1轮排序
// 因为第1轮排序，是将10个数据分成了5组--> 10/2
for (int i = 5; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素)，步长为5
for (int j = i-5; j >= 0; j -= 5) {
// 为什么此处-=5会退出，因为每组数据只有2个数据，比较完就退出了
// 如果当前元素大于加上步长后的那个元素，要交换
if (arr[j] > arr[j+5]) {
temp = arr[j];
arr[j] = arr[j+5];
arr[j+5] = temp;
}
}
}
// 3 5 1 6 0 8 9 4 7 2
System.out.println("希尔排序1轮后："+Arrays.toString(arr));
// 希尔排序的第2轮排序
// 因为第2轮排序，是将10个数据分成了2组--> 10/5/2
for (int i = 2; i < arr.length; i++) {// 此处不断增量，代表初始最大比较位置不断变化
// 遍历各组中所有的元素(共2组，每组有5个元素)，步长为2
// 步长是2，但是要从下标0开始
// 第1次 j=2-2，比较的是 arr[0] arr[0+2] 第1组
// 第2次 j=3-2，比较的是 arr[1] arr[1+2] 第2组
// 第3次 j=4-2，比较的是 arr[2] arr[2+2] 第1组
// 第4次 j=5-2，比较的是 arr[3] arr[3+2] 第2组
// 第5次 j=6-2，比较的是 arr[4] arr[4+2] 第1组
// ....依次类推，将2组中的每组5个元素都分别比较完
for (int j = i-2; j >= 0; j -= 2) {
// -=2这个步长设置的作用，是分组数据的作用
// 遍历的目的是，当不断比较的时候，每组中需要比较
// 的数据需要每次在当前循环中所有数据进行遍历比较
// 如果当前元素大于加上步长后的那个元素，要交换
if (arr[j] > arr[j+2]) {
temp = arr[j];
arr[j] = arr[j+2];
arr[j+2] = temp;
}
}
}
// 0 2 1 4 3 5 7 6 9 8
System.out.println("希尔排序2轮后："+Arrays.toString(arr));
// 希尔排序的第3轮排序
// 因为第3轮排序，是将10个数据分成了1组--> 10/5/2/2
for (int i = 1; i < arr.length; i++) {
for (int j = i-1; j >= 0; j--) {
// 如果当前元素大于加上步长后的那个元素，要交换
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
System.out.println("希尔排序3轮后："+Arrays.toString(arr));
}
}
希尔排序(交换法)通用代码如下：速度比移步法慢 本质是分组+冒泡排序
package sort2;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shellSort(arr);
}
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
// 根据前面的逐步分析，使用循环处理
for (int gap = arr.length/2; gap > 0; gap /= 2) {// 此处是分组的作用
// 遍历各组中所有的元素(共gap组，每组有n个元素)，步长为gap
// 外层for用于递增找到所有的元素
// 内层for用于递减步长比较所有元素
for (int i = gap; i < arr.length; i++) {
for (int j = i-gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，要交换
if (arr[j] > arr[j+gap]) {// +gap的目的是为了分组内元素进行比较
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
System.out.println("希尔排序"+(++count)+"轮后："+Arrays.toString(arr));
}
}
}
希尔排序(移位法)代码如下：通用代码 本质是分组+插入排序
package sort2;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
// 使用逐步推导的方式编写希尔排序
// 对交换式的希尔排序进行优化--> 移位法
public static void shellSort(int[] arr) {
// 增量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]) {// 为什么此处用temp而不用arr[j]
// 移动
arr[j] = arr[j-gap];
j -= gap;
}
// 当退出while循环时，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
}
