java排序算法（八）：希尔排序（shell排序）
希尔排序（缩小增量法）属于插入类排序，由shell提出，希尔排序对直接插入排序进行了简单的改进，它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度的移动。当着写数据项拍过一趟序之后，希尔排序算法缩小数据项的间隔再进行排序，一次进行下去。进行这些排序时的数据项直接的间隔被称为增量，习惯上用字母h来表示增量
常用的h序列有Knuth提出，该序列从1开始，通过如下公式产生
h=3*h+1;
反过来程序需要反向计算h的值
h = h-1/3
代码实现
package com.spring.test; /**
* 希尔排序
*/
public class ShellSortTest {
public static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
shellSort(data);
System.out.println("排序后的结果");
print(data);
} /**
* 希尔排序
* @param data
*/
public static void shellSort(int[] data){
//计算出最大的h值
int h = 1;
while(h < data.length/3){
h = h*3+1;
}
while(h > 0){
for(int i = h;i<data.length;i+=h){
if(data[i] < data[i-h]){
int tmp = data[i];
int j = i-h;
while(j >=0 && data[j] >tmp){
data[j+h] =data[j];
j-=h;
}
data[j+h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
} /**
* 打印输出
*/
public static void print(int[] data){
for(int i=0;i<data.length;i++){
System.out.print(data[i]+"\t");
}
System.out.println();
}
}
运算结果