希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
假设原始数组arr数据如下
初始增量gap=arr.length/2=8/2=4,意味着整个数组被分为4组，这四组分别使用插入排序如下
继续进行增量排序gap=gap/2=4/2=2,,数组被重新分组为两组，对这两组使用插入排序继续进行排序
直到增量排序gap=1时，将数组分为一组，数组无法再进行增量排序，则进行最后一次排序
经过最后一次的排序，整体宏观调控，微型调整，即可完成排序
在我们的增量排序过程，对我们每一组的数据进行排序，这里可使用直接插入法和交换法两种，但是，直接插入法效率远高于交换法，所以在对分组数据排序时，建议使用直接插入法
代码实现
/**
* 希尔排序
*/
@Test
public void testShellSort() {
int[] arr = new int[]{1, 4, 6, 3, 8, 9, 2, 23};
exchangeShellSort(arr);
// insertShellSort(arr);
}
/**
* 希尔排序-交换法
* @param arr
*/
public void exchangeShellSort(int arr[]) {
int temp;//临时数据
boolean flag = false;//是否交换
int count = 1;//计数
// 分而治之，将数值分组排序,i为步长
for (int i = arr.length / 2; i > 0; i /= 2) {
// 遍历分治的每一个分组
for (int j = i; j < arr.length; j++) {
// 遍历分治的每一个分组的每一个值
for (int k = j - i; k >= 0; k -= i) {
if (arr[k + i] < arr[k]) {
temp = arr[k + i];
arr[k + i] = arr[k];
arr[k] = temp;
flag = true;
}
if (!flag) {
break;
} else {
// 为了下次判断
flag = false;
}
}
}
System.out.println("希尔排序交换法第" + (count++) + "次排序后" + Arrays.toString(arr));
}
}交换过程
代码实现
/**
* 希尔排序
*/
@Test
public void testShellSort() {
int[] arr = new int[]{1, 4, 6, 3, 8, 9, 2, 23};
// exchangeShellSort(arr);
insertShellSort(arr);
}
/**
* 希尔排序-插入法
* @param arr
*/
public void insertShellSort(int[] arr) {
int count = 1;//计数
// 分而治之，循环为每次总数除二
for (int i = arr.length / 2; i > 0; i /= 2) {
// 循环分治的每一个分组
for (int j = i; j < arr.length; j++) {
int index = j;
int temp = arr[index];
// 比较每一组的值
if (arr[index] < arr[index - i]) {
// 如果比前面小就把前面的数值往后移，将合适的数值插入
while (index - i > 0 && temp < arr[index - i]) {
arr[index] = arr[index - i];
index -= i;
}
arr[index] = temp;
}
}
System.out.println("希尔排序插入法第" + (count++) + "次排序后" + Arrays.toString(arr));
}
}排序过程
