希爾排序及其優(yōu)化

算法簡介

希爾排序的由來：1959 年 Shell 發(fā)明；第一個突破 O(n^2) 的排序算法；是簡單插入排序的改進(jìn)版；它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。

基本思路

希爾排序?yàn)榱思涌焖俣群唵蔚母倪M(jìn)了插入排序，交換不相鄰的元素以對數(shù)組的局部進(jìn)行排序，并最終用插入排序將局部有序的數(shù)組排序。（局部有序的數(shù)組很適合插入排序）

Q：希爾排序的思想？
A：使數(shù)組中任意間隔為 h 的元素都是有序的。這樣的數(shù)組被稱為 h 有序數(shù)組，也就是說：一個 h 有序數(shù)組就是 h 個相互獨(dú)立的有序數(shù)組編織在一起組成的一個數(shù)組。

Q：它的一種實(shí)現(xiàn)方法？
A：在插入排序的代碼中將移動元素的距離由 1 改為 h 即可。

Q：h 的取值？
A：增幅 h 的初始值是數(shù)組長度乘以一個常數(shù)因子，最小為 1 。 例如： while( h < arr.length/3 ) h = 3 * h + 1 ； //（1、4、13、40、121、364、1093…）
嘗試使用 while( h < arr.length/5 ) h = 5 * h + 1 ；// 1、6、31、156、781... ，速度會變快。

優(yōu)點(diǎn)：希爾排序?qū)τ谥械却笮〉臄?shù)組，運(yùn)行時間是可以接受的，代碼量少，且不需要使用額外的內(nèi)存空間。

運(yùn)行軌跡

增幅 h 的初始值是數(shù)組長度乘以一個常數(shù)因子，最小為 1 。
當(dāng) h = 4 時，4-sort；
當(dāng) h = 1 時，1-sort；


h 的增幅：1、4、13、40、121、364、1093…
希爾排序，僅供參考，遞增數(shù)列與本文不同

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

根據(jù)排序算法類的模板實(shí)現(xiàn)希爾排序（提醒：點(diǎn)藍(lán)字查看詳情）

import java.util.Random;

/**
 * 希爾排序
 *
 * @author TinyDolphin
 *         2017/5/30 22:33.
 */
public class Shell {
    /**
     * 排序?qū)崿F(xiàn)
     *
     * @param arr 待排序數(shù)組
     */
    public static void sort(Comparable[] arr) {
        int length = arr.length;
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;  // 1 , 4 , 13 , 40 , 121 , 364 , 1093...
        }
        while (h >= 1) {
            // 將數(shù)組變?yōu)?h 有序
            for (int indexI = h; indexI < length; indexI++) {
                for (int indexJ = indexI; indexJ >= h && less(arr[indexJ], arr[indexJ - h]); indexJ -= h) {
                    exch(arr, indexJ, indexJ - h);
                }
            }
            h = h / 3;
        }
    }

    /**
     * 比較兩個元素的大小
     *
     * @param comparableA 待比較元素A
     * @param comparableB 待比較元素B
     * @return 若 A < B,返回 true,否則返回 false
     */
    private static boolean less(Comparable comparableA, Comparable comparableB) {
        return comparableA.compareTo(comparableB) < 0;
    }

    /**
     * 將兩個元素交換位置
     *
     * @param arr    待交換元素所在的數(shù)組
     * @param indexI 第一個元素索引
     * @param indexJ 第二個元素索引
     */
    private static void exch(Comparable[] arr, int indexI, int indexJ) {
        Comparable temp = arr[indexI];
        arr[indexI] = arr[indexJ];
        arr[indexJ] = temp;
    }

    /**
     * 打印數(shù)組的內(nèi)容
     *
     * @param arr 待打印的數(shù)組
     */
    private static void show(Comparable[] arr) {
        for (int index = 0; index < arr.length; index++) {
            System.out.print(arr[index] + " ");
        }
        System.out.println();
    }

    /**
     * 判斷數(shù)組是否有序
     *
     * @param arr 待判斷數(shù)組
     * @return 若數(shù)組有序，返回 true，否則返回 false
     */
    public static boolean isSort(Comparable[] arr) {
        for (int index = 1; index < arr.length; index++) {
            if (less(arr[index], arr[index - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[100000];
        for (int index = 0; index < 100000; index++) {
            arr[index] = new Random().nextInt(100000) + 1;
        }
        long start = System.currentTimeMillis();
        sort(arr);      //耗費(fèi)時間：480ms
        long end = System.currentTimeMillis();
        System.out.println("耗費(fèi)時間：" + (end - start) + "ms");
        assert isSort(arr);
    }
}

性能分析

最佳情況：T(n) = O(nlog2n)
最壞情況：T(n) = O(nlog2n)
平均情況：T(n) = O(nlogn)

算法的性能不僅取決于 h ， 還取決于 h 之間的數(shù)學(xué)性質(zhì)，比如它們的公因子等。

使用遞增序列 1、4、13、40、121、364… 的希爾排序所需的比較次數(shù)不會超過 N 的若干倍乘以遞增序列的長度。

Q：如何通過h遞增序列優(yōu)化？
A：在實(shí)際應(yīng)用中，h 的取值使用以上遞增序列基本就足夠了。但是我們?yōu)榱俗非笮阅艿奶嵘?，也使用以下的序列，使性能提?20%-40% 。1、5、19、41、109、209、505、929、2161、3905、8929、16001、36289、64769、146305、260609（這是通過 9×4k-9×2k+1(k=1,2,3,4,5…) 和 4k-3×2k+1(k=2,3,4,5,6…) 綜合得到的）

Q：希爾排序?yàn)槭裁锤痈咝В?/strong>
A：它權(quán)衡了子數(shù)組的規(guī)模和有序性。

Q：和選擇排序以及插入排序形成對比的是：
A：希爾排序也可以用于大型數(shù)組。它對任意排序（不一定是隨機(jī)的）的數(shù)組表現(xiàn)也很好。希爾排序比插入排序和選擇排序要快的多，并且數(shù)組越大，優(yōu)勢越大?！咎崾荆狐c(diǎn)擊藍(lán)色字體，可以查看其詳細(xì)信息?！?/p>

Q：什么時候用希爾排序？
A： 當(dāng)你需要解決一個排序問題而又沒有系統(tǒng)排序函數(shù)可用（例如直接接觸硬件或是運(yùn)行于嵌入式系統(tǒng)中的代碼）時，可用先用希爾排序，然后再考慮是否值得將它替換為更加復(fù)雜的排序算法。

※ 研究算法的設(shè)計和性能的主要原因之一：通過提升速度來解決其他方式無法解決的問題。

優(yōu)化方案

NO.1

使用更為復(fù)雜的遞增序列，性能可以提高 20%-40% 。（這里就不說了，上述的遞增序列夠用）

NO.2

因?yàn)槭腔诓迦肱判虻?，所以可以使用?a href="http://www.itdecent.cn/p/df8fac515214" target="_blank">插入排序及其優(yōu)化中給出的優(yōu)化方案。即：進(jìn)行了預(yù)處理操作，并在內(nèi)循環(huán)中，總是將較大的元素向右移動。原方案是交換。

優(yōu)化之后運(yùn)行軌跡
希爾排序優(yōu)化方案
優(yōu)化之后代碼
   public static void sortPlus(Comparable[] arr) {
        int length = arr.length;
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;  // 1 , 4 , 13 , 40 , 121 , 364 , 1093...
        }
        int exchanges = 0; //交換次數(shù)
        //若 arr[index] < arr[index - 1]，則交換兩數(shù)
        for (int index = length - 1; index > 0; index--) {
            if (less(arr[index], arr[index - 1])) {
                exch(arr, index, index - 1);
                exchanges++;
            }
        }
        //若交換次數(shù)為0（即數(shù)組有序），則無需進(jìn)行下一步排序。
        if (exchanges == 0) return;
        //若有交換次數(shù)，表明目前的數(shù)組無序。
        while (h >= 1) {
            // 將數(shù)組變?yōu)?h 有序
            for (int indexI = h; indexI < length; indexI++) {
                Comparable temp = arr[indexI];  //記錄一下arr[indexI]的值
                int indexJ = indexI;            //indexI 的代替品
                //若 indexJ 的前 h 位元素小于 temp，則將小于temp的元素向右移動 h 位
                //需要注意：可能會出現(xiàn) indexJ < h 的情況。而一般的插入排序不會出現(xiàn)。
                while (indexJ >= h && less(temp, arr[indexJ - h])) {
                    arr[indexJ] = arr[indexJ - h];
                    indexJ -= h;
                }
                arr[indexJ] = temp; //將記錄的值放在 indexJ 的位置上
            }
            h = h / 3;
        }
    }
測試代碼

【高效復(fù)制數(shù)組的方法】，提示：點(diǎn)擊藍(lán)色字體查看方法詳情。

    public static void main(String[] args) {
        int length = 1000000;  // 百萬數(shù)據(jù)量級別
        Integer[] arr = new Integer[length];
        Integer[] arr2 = new Integer[length];
        for (int index = 0; index < length; index++) {
            arr[index] = new Random().nextInt(length) + 1;
        }
        //高效復(fù)制數(shù)組的方法
        System.arraycopy(arr, 0, arr2, 0, arr.length);

        long start = System.currentTimeMillis();
        sort(arr);  
        long end = System.currentTimeMillis();
        System.out.println("耗費(fèi)時間：" + (end - start) + "ms");
        assert isSort(arr);

        start = System.currentTimeMillis();
        sortPlus(arr2);
        end = System.currentTimeMillis();
        System.out.println("耗費(fèi)時間：" + (end - start) + "ms");
        assert isSort(arr2);
    }
測試結(jié)果
百萬數(shù)據(jù)量級別測試結(jié)果

注意：編譯器默認(rèn)不適用 assert 檢測（但是junit測試中適用），所以要使用時要添加參數(shù)虛擬機(jī)啟動參數(shù)-ea
具體添加過程，請參照eclipse 和 IDEA 設(shè)置虛擬機(jī)啟動參數(shù)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個記錄插入到已排序好...
    依依玖玥閱讀 1,349評論 0贊 2
  • 概述 排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    蟻前閱讀 5,300評論 0贊 52
  • 概述：排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    每天刷兩次牙閱讀 3,824評論 0贊 15
  • 一、 單項(xiàng)選擇題（共71題） 對n個元素的序列進(jìn)行冒泡排序時，最少的比較次數(shù)是（ ）。A. n ...
    貝影閱讀 9,424評論 0贊 10
  • 染色過的記憶 已無法分辨真?zhèn)?更無力分揀 只能胡亂的裝在麻袋里 丟棄在陰暗的角落 任其發(fā)霉，腐爛 春天來的時候 從...
    冷冬年閱讀 496評論 4贊 7

友情鏈接更多精彩內(nèi)容