希爾排序

一種基于插入排序的快速的排序算法。簡單插入排序?qū)τ诖笠?guī)模亂序數(shù)組很慢，因?yàn)樵刂荒芤稽c(diǎn)一點(diǎn)地從數(shù)組的一端移動(dòng)到另一端。例如，如果主鍵最小的元素正好在數(shù)組的盡頭，要將它挪到正確的位置就需要n-1次移動(dòng)。

希爾排序?yàn)榱思涌焖俣群唵蔚馗倪M(jìn)了插入排序，也稱為縮小增量排序。

希爾排序是把待排序數(shù)組按一定的數(shù)量分組，對每組使用直接插入排序算法排序；然后縮小數(shù)量繼續(xù)分組排序，隨著數(shù)量逐漸減少，每組包含的元素越來越多，當(dāng)數(shù)量減至 1 時(shí)，整個(gè)數(shù)組恰被分成一組，排序便完成了。這個(gè)不斷縮小的數(shù)量，就構(gòu)成了一個(gè)增量序列，這里的數(shù)量稱為增量。

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

public class ShellSort {

    public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};

    public static int[] sort(int[] array) {
        int len = array.length;
        if (len < 2) {
            return array;
        }
        //當(dāng)前待排序數(shù)據(jù)，該數(shù)據(jù)之前的已被排序
        int current;
        //增量
        int gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                //前面有序序列的索引
                int index = i - gap;
                while (index >= 0 && current < array[index]) {
                    array[index + gap] = array[index];
                    //有序序列的下一個(gè)
                    index -= gap;
                }
                //插入
                array[index + gap] = current;
            }
            //int相除取整
            gap = gap / 2;
        }
        return array;
    }


    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

時(shí)間復(fù)雜度

希爾排序的復(fù)雜度和增量序列有關(guān)。

在先前較大的增量下每個(gè)子序列的規(guī)模都不大,用直接插入排序效率都較高，盡管在隨后的增量遞減分組中子序列越來越大,由于整個(gè)序列的有序性也越來越明顯,則排序效率依然較高。

從理論上說，只要一個(gè)數(shù)組是遞減的，并且最后一個(gè)值是1，都可以作為增量序列使用。有沒有一個(gè)步長序列,使得排序過程中所需的比較和移動(dòng)次數(shù)相對較少,并且無論待排序列記錄數(shù)有多少,算法的時(shí)間復(fù)雜度都能漸近最佳呢？但是目前從數(shù)學(xué)上來說，無法證明某個(gè)序列是最好的。

常用的增量序列：

• 希爾增量序列 ：{n/2, (n / 2)/2, …, 1}，其中N為原始數(shù)組的長度，這是最常用的序列，但卻不是最好的
• Hibbard序列：{2k-1, …, 3,1}
• Sedgewick序列：{… , 109 , 41 , 19 , 5，1} 表達(dá)式為9 * 4i- 9 * 2i + 1，i = 0，1，2，3，4…

算法穩(wěn)定性

由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動(dòng)，如數(shù)組5，2，2，1，第一次排序第一個(gè)元素5會和第三個(gè)元素2交換，第二個(gè)元素2會和第四個(gè)元素1交換，原序列中兩個(gè)2的相對前后順序就被破壞了，所以希爾排序是一個(gè)不穩(wěn)定的排序算法。

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評論