希尔排序

1959年Shell发明，第一个突破 O(n2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

08.gif

实例

代码实现

public class ShellTest {
    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;
       }
    }
}