Johnny

/**
 * 希爾排序
 * @author sikaijian
 */
public class ShellSort {
    public static void sort(int[] data){
        int d = data.length/2;
        while(d!=0){
            directInsertSort(data, d);
            d/=2;
        }
    }
    
    /**
     * 帶增量的直接插入排序
     * @param data 待排序數組
     * @param d 增量
     */
    private static void directInsertSort(int[] data, int d){
        int len = data.length;
        
        for(int i=0; i+d<len; i++){
            int pCurrent = i+d;
            int left = i-1;
            while(pCurrent<len){
                int front = pCurrent-d;
                int key = data[pCurrent];
                while(front>left && data[front]>key){
                    data[front+d] = data[front];
                    front-=d;
                }
                data[front+d] = key;
                
                pCurrent+=d;
            }
        }
    }
    
    public static void showArray(int[] array){
        for (int t : array) {
            System.out.print(t);
            System.out.print(" ");
        }
    }
    
    /**
     * 測試代碼
     * @param args
     */
    public static void main(String[] args) {
        int[] data = new int[] { 49, 23, 65, 13, 38, 96, 12, 33, 88, 123, 22,
                11, 9, 55, 111, 0 };

        showArray(data);
        System.out.println();
        System.out.println("------------------------------");
        ShellSort.sort(data);

        showArray(data);
    }
}