简介
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
关键人物：Donald Shell
发布时间：1959
希尔排序算法的原理
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
例
希尔排序算法图示
如图，所示，第一次分组分为3组，距离为3，第一趟排序结果为三组各自插入排序结果的叠加。后面几趟和一趟排序一样处理，只是距离在改变，因此组数改变，组内成员数改变而已。
希尔排序算法的Java实现
先来讨论下几个重要的变量：
- 整个希尔排序需要几趟？数组序列长度（分组序列的长度）/2，一直到这个结果等于1为止
- 距离为d时，能分几组？数组长度/d
- 距离为d时，每组的有几个元素？（数组长度-趟数-1）/d
- 当前元素和同组下一个元素的下标关系？nextIndex=index+d
核心代码
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
//设置距离，分组的组数也是distance
int distance = data.length / 2;
while (distance > 0) {
int group = distance;
//每组的第一个元素下表和组数相同
for (int g = 0; g < group; g++) {
//每组的成员数
int member = (data.length - g) / distance;
//下面的过程和插入排序原理一样（每次插入一个元素，然后内部排序）
for (int i = 0; i < member; i++) {
int index = i * distance + g;
int nextIndex = index + distance;
if (nextIndex > data.length - 1) break;
if (super.compare(data, index, nextIndex, isAscending)) {
this.doSwap(data, index, nextIndex, isAscending);
} else {
continue;
}
for (int j = i; j > 0; j--) {
this.doSwap(data, (j - 1) * distance, j * distance, isAscending);
}
}
}
//减少增量，方式可以任意改变，比如distance--，distance = distance / 4都可以
distance = distance / 2;
}
}
全部代码
AbstractSort.java
public abstract class AbstractSort {
private int[] data;
public AbstractSort(int[] data) {
this.data = data;
}
public abstract void sort(boolean isAscending);
public void sort() {
this.sort(true);
}
public int[] getData() {
return data;
}
public void print() {
for (int i : this.data) {
System.out.println(i);
}
}
protected void swap(int[] data, int indexA, int indexB) {
int temp = data[indexA];
data[indexA] = data[indexB];
data[indexB] = temp;
}
}
InsertionSort.java（插入排序算法，希尔排序算法可以基于此算法实现）
public class InsertionSort extends AbstractSort {
public InsertionSort(int[] data) {
super(data);
}
@Override
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
for (int i = 0; i < data.length - 1; i++) {
if (this.compare(data, i, i + 1, isAscending)) {
this.doSwap(data, i, i + 1, isAscending);
} else {
continue;
}
for (int j = i; j > 0; j--) {
this.doSwap(data, j - 1, j, isAscending);
}
}
}
protected boolean compare(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
return largeThan && isAscending || !largeThan && !isAscending;
}
protected void doSwap(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
if (largeThan && isAscending || !largeThan && !isAscending) {
super.swap(data, indexA, indexB);
}
}
}
ShellsSort.java（继承于插入排序算法）
public class ShellsSort extends InsertionSort {
public ShellsSort(int[] data) {
super(data);
}
@Override
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
//设置距离，分组的组数也是distance
int distance = data.length / 2;
while (distance > 0) {
int group = distance;
//每组的第一个元素下表和组数相同
for (int g = 0; g < group; g++) {
//每组的成员数
int member = (data.length - g) / distance;
//下面的过程和插入排序原理一样（每次插入一个元素，然后内部排序）
for (int i = 0; i < member; i++) {
int index = i * distance + g;
int nextIndex = index + distance;
if (nextIndex > data.length - 1) break;
if (this.compare(data, index, nextIndex, isAscending)) {
this.doSwap(data, index, nextIndex, isAscending);
} else {
continue;
}
for (int j = i; j > 0; j--) {
this.doSwap(data, (j - 1) * distance, j * distance, isAscending);
}
}
}
distance = distance / 2;
}
}
}
