摘要：概述希爾排序的誕生是由于插入排序在處理大規(guī)模數(shù)組的時(shí)候會遇到需要移動太多元素的問題，也稱遞減增量排序算法。希爾排序的思想是將一個大的數(shù)組分而治之，劃分為若干個小的數(shù)組，然后分別對劃分出來的數(shù)組進(jìn)行插入排序。

希爾排序的誕生是由于插入排序在處理大規(guī)模數(shù)組的時(shí)候會遇到需要移動太多元素的問題，也稱遞減增量排序算法。希爾排序的思想是將一個大的數(shù)組“分而治之”，劃分為若干個小的數(shù)組，然后分別對劃分出來的數(shù)組進(jìn)行插入排序。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率

但插入排序一般來說是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位

效果示意圖：

至于如何提高效率的，我們還是看下面的實(shí)例吧。

取增量，一般取數(shù)組長度/2

按增量取得一個子數(shù)列，對子數(shù)列按插入排序的方式處理

將增量遞減，重復(fù)1,2步驟

直至增量為為0，數(shù)列已經(jīng)排好序

原始數(shù)據(jù)：

3 5 2 6 2

取5/2=2作為增量，對[3 2 2]進(jìn)行插入排序，得到

2 5 2 6 3

增量遞減2/2=1，對[2 5 2 6 3]進(jìn)行插入排序，得到

2 2 3 5 6

增量遞減為0，排序結(jié)束。

package com.coder4j.main.arithmetic.sorting;
    
public class Shell {
    
    /**
     * 希爾排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        int step = array.length / 2;
        while (step >= 1) {
            for (int i = step; i < array.length; i++) {
                int temp = array[i];
                int j;
                for (j = i - step; j >= 0 && temp < array[j]; j-=step) {
                    array[j + step] = array[j];
                }
                array[j + step] = temp;
            }
            System.out.println("增量為：" + step + ",結(jié)果：");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
            step /= 2;
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結(jié)果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

測試輸出結(jié)果：

增量為：2,結(jié)果：
2 5 2 6 3 
增量為：1,結(jié)果：
2 2 3 5 6 
最終結(jié)果
2 2 3 5 6 

經(jīng)測試，與實(shí)例中結(jié)果一致。

希爾是插入的改進(jìn)優(yōu)化，到底能否提高效率呢，我們作一下小測試。

分別對[1 2 3 4] 和 [4 3 2 1] 進(jìn)行兩種算法的排序操作，看移動的次數(shù)。

比較代碼：

package com.coder4j.main.arithmetic.sorting;

public class ShellVSInsert {

    /**
     * 插入排序
     * 
     * @param array
     * @return
     */
    public static int[] insert(int[] array) {
        // 記錄移動次數(shù)
        int count = 0;
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j;
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
                count++;
            }
            array[j + 1] = temp;
        }
        System.out.println("插入排序移動次數(shù)：" + count);
        for (int k : array) {
            System.out.print(k + " ");
        }
        System.out.println();
        return array;
    }
    
    /**
     * 希爾排序
     * 
     * @param array
     * @return
     */
    public static int[] shell(int[] array) {
        // 記錄移動次數(shù)
        int count = 0;
        int step = array.length / 2;
        while (step >= 1) {
            for (int i = step; i < array.length; i++) {
                int temp = array[i];
                int j;
                for (j = i - step; j >= 0 && temp < array[j]; j = j - step) {
                    array[j + step] = array[j];
                    count++;
                }
                array[j + step] = temp;
            }
            step /= 2;
        }
        System.out.println("希爾排序移動次數(shù)：" + count);
        for (int k : array) {
            System.out.print(k + " ");
        }
        System.out.println();
        return array;
    }
    
    public static void main(String[] args) {
        int[] array1 = { 1, 2, 3, 4 };
        insert(array1);
        int[] array2 = { 1, 2, 3, 4 };
        shell(array2);
        
        int [] array3 = { 4, 3, 2, 1 };
        insert(array3);
        int [] array4 = { 4, 3, 2, 1 };
        shell(array4);
        
    }
    
}

對比了兩種極端情況，結(jié)果如下：

插入排序移動次數(shù)：0
1 2 3 4 
希爾排序移動次數(shù)：0
1 2 3 4 
插入排序移動次數(shù)：6
1 2 3 4 
希爾排序移動次數(shù)：4
1 2 3 4 

可見希爾排序在有些時(shí)候可以減少移動次數(shù)。