希尔排序(交换法&移位法)
一. 引入
我们看简单的插入排序可能存在的问题，数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小)，当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响，这时就需要更加高效的插入排序，希尔排序。
二. 希尔排序介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
三. 希尔排序基本思想
希尔排序是把记录按下标的一定增量(增量就是gap)分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单来说，就是按照增量的间隔得到两个数，然后比较这个两个数的大小，在根据自己定义的规则，看看是否需要交换数据。
思路分析图
四. 交换法核心代码
//希尔排序(交换法)
public static void shellSort(int[] arr){
//gap:增量,间隔的步数
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]){
//判断成立 交换
int temp = arr[j + gap];
arr[j + gap] = arr[j];
arr[j] = temp;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
五. 移位法核心代码
//希尔排序(移位法)
public static void shellSort2(int[] arr){
//gap:增量,间隔的步数
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;
}
//小的数移到前面,当前这j是在while循环中减完步数后的，相当于是arr[j-gap]
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
总结: 移位法和交换法最大的不同是效率，移位法效率高，如果有什么不懂可以带入几个数据，把代码走一遍，就会了。
https://github.com/jmstart/DataStructures/blob/master/DataStructures/src/com/jiaming/sort/ShellSort2.java