希尔排序是插入排序的一个变种。对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
先看一段希尔排序的实现的代码：
public static void ShellSort1() {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
// 希尔排序
int d = a.length;
while (true) {
d = d / 2;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < a.length; i = i + d) {
int temp = a[i];
int j;
for (j = i - d; j >= 0 && a[j] > temp; j = j - d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d == 1) {
break;
}
}
}
这段代码有三层循环，下面我们将其进行分解。
第一步，先是一个基本的插入排序的算法：
public static void InserSort1(int[] a){
for(int i=1;i<a.length;i=i+1){
int temp = a[i];
int j=i-1;
while(j>=0&&temp<a[j]){
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
}
将其进行改进，改为可以指定步进长度，也就是把原来所有出现的“1”都改为“d”。
这样就将默认的步进长度，由“依次”改为人为指定长度d。
public static void InserSort1(int[] a,int d){
for(int i=d;i<a.length;i=i+d){
int temp = a[i];
int j=i-d;
while(j>=0&&temp<a[j]){
a[j+d]=a[j];
j=j-d;
}
a[j+d]=temp;
}
}
第二步，确定步进长度d，采用缩减式。每次缩减为原长度的某个比例。可固定为一半，即divid=2。
public static int MakeSetpLength(int d,int divid){
d=d/divid;
return d;
}
第三步，组合。由大到小的采用一系列步进长度d，当d==1时，再进行最后一次插入排序，然后结束。
public static void ShellSort(int[] a){
int d=a.length;
while(true){
int divid=2;//可以改为变化的缩进，如2，3，5，8...这样的缩进方式。
//这种方式需要记录原长度a.length
d=MakeSetpLength(d,divid);
InserSort1(a,d);
if(d==1){
break;
}
}
}
完整代码如下：
package asen.yang;
public class shellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
ShellSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static void ShellSort0(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && a[j].compareTo(a[j - h]) < 0; j = j - h) {
Comparable temp = a[j];
a[j] = a[j - h];
a[j - h] = temp;
}
}
h = h / 3;
}
}
public static void InserSort1(int[] a){
for(int i=1;i<a.length;i++){
int temp = a[i];
int j=i-1;
while(j>=0&&temp<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
public static void InserSort1(int[] a,int d){
for(int i=d;i<a.length;i=i+d){
int temp = a[i];
int j=i-d;
while(j>=0&&temp<a[j]){
a[j+d]=a[j];
j=j-d;
}
a[j+d]=temp;
}
}
public static int MakeSetpLength(int d,int divid){
d=d/divid;
return d;
}
public static void ShellSort(int[] a){
int d=a.length;
while(true){
int divid=2;//可以改为变化的缩进，如2，3，5，8...这样的缩进方式。这种方式需要记录原长度a.length
d=MakeSetpLength(d,divid);
InserSort1(a,d);
if(d==1){
break;
}
}
}
public static void ShellSort1() {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
// 希尔排序
int d = a.length;
while (true) {
d = d / 2;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < a.length; i = i + d) {
int temp = a[i];
int j;
for (j = i - d; j >= 0 && a[j] > temp; j = j - d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d == 1) {
break;
}
}
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
在上面的代码中，有一个ShellSort0的实现，这种方式在某些教材中出现，但是不好理解。有需要的朋友可以参考一下。