【Java -- 算法】十大排序算法之希尔排序

简介

插入排序对于大规模的乱序数组，插入排序会很慢，因为它只会交换相邻的元素，元素只能一点一点的从数组的一端移动到另一端。如果最小的元素在数组的末尾，则要将它移动到数组的开头则需要进行n-1次移动。

希尔排序改进了插入排序这一问题，它交换不相邻的元素对数组进行局部排序，并最终用插入排序将局部有序的数组进行排序。
希尔排序的思想就是使得数组中任意间隔h的元素都是有序的，这样的数组可以成为h有序数组。这里拿数组a={4,8,9,1,10,6,2,5}为例，当h为4时，会将这个数组分为h个子数组。

实例

1. Java 代码

public class Main {
public static void main(String[] args) {
int[] sort ={3,2,1,4,6,5,8,9,10,7} ;
System.out.println("排序前：");
printArray(sort);
shellSort(sort);
System.out.println("\n排序后：");
printArray(sort);
}

public static void printArray(int[] a) {
for (int i = 0;i < a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}

public static void shellSort(int[] data){
int h = 1;
int len = data.length;

while(h < len/3) {
h = h * 3 + 1;
}

while(h > 0) {
int in,out;
for (out = h;out < data.length;out++) {
int tmp = data[out];
for(in = out - h;in >= 0 &&data[in] > tmp;in -= h) {
data[in + h] = data[in];
}
data[in + h] = tmp;
}
h = (h-1) / 3;
}
}


}

2. 输出结果