基本思想

希爾排序是把記錄按下表的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

實(shí)現(xiàn)步驟

• 計(jì)算數(shù)組中間值，劃分間隔gap
• 按照gap間隔，劃分為新的子序列
• 分別使用插入排序，使每個(gè)子序列變得相對(duì)有序
• 減少間隔gap，重復(fù)步驟2、3

劃分序列

實(shí)現(xiàn)代碼

public class Shell_Sort {

    public static void shell_sort(int[] array){
        if (array==null||array.length<=0){
            return;
        }
        int length = array.length;
        int gap=length/2;
        int temp = 0;
        while (gap>0){
            for (int i = gap; i <length; i++) {
                temp = array[i];
                int preIndex = i-gap;
                while (preIndex>=0&& array[preIndex]>temp){
                    array[preIndex+gap] = array[preIndex];
                    preIndex-=gap;
                }
                array[preIndex+gap]=temp;
            }
            gap /=2;
        }


    }
    public static void main(String[] args) {
        int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

        shell_sort(array);
        System.out.println(Arrays.toString(array));
    }
}