一、排序的概念

排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

排序的穩(wěn)定性

上述待排序的數(shù)中，有兩個5。 將前面的5標記一個a， 將后面的5標記一個b。

通過算法進行排序后，這一組數(shù)就有序了， 但是要看兩個相同的5的位置是否有改變。
5a仍在5b前面，那么這個排序算法就是穩(wěn)定的 ，
5a跑到了5b后面，那么這個排序算法就是不穩(wěn)定的 。
一個穩(wěn)定的排序算法可以做到不穩(wěn)定，
不穩(wěn)定的排序算法一定做不到穩(wěn)定。

至于為什么要討論這個穩(wěn)定性， 是為了以后應(yīng)用到實際場景上。 比如，一場數(shù)學(xué)考試， 假設(shè)a用了30分鐘做完了，并得了滿分。
假設(shè)b用了一個小時做完了，并得了滿分。 此時a與b都是得了滿分，但是用的時間不一樣，所以兩個人的排名又會有所不同。

七大排序算法

二、希爾排序

核心思想

基本思想： 希爾排序法又稱縮小增量法。希爾排序法的基本思想是：

先選定一個整數(shù)，把待排序文件中所有記錄分成多個組。
所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行直接插入排序。
然后，取，重復(fù)上述分組和排序的工作。
當?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

圖解

有一組待排序數(shù)列，我們進行升序排序。
排序過程：
說白了就是，將這些數(shù)分為幾個組，這幾個組再分別直接插入排序，然后分的組數(shù)減少，重復(fù)上述過程，直到只剩1組時，再對這個組排序，就完成了排序。

組數(shù)多則每組的數(shù)據(jù)少，組數(shù)少則每組的數(shù)據(jù)多。

代碼實現(xiàn)

代碼實現(xiàn)

public class ShellSort {
    /**
     * 希爾排序
     * 時間復(fù)雜度：O（n^1.3） - O(n^1.5)
     * 空間復(fù)雜度：O(1)
     * 穩(wěn)定性：不穩(wěn)定
     * @param array
     */
    public static void shell(int[] array) {
        // 組數(shù)
        int gap = array.length;
        while (gap > 1) {
            // gap組數(shù)變換比較隨意，
            // gap /= 3;也可以
            gap /= 2;
            shell(array,gap);
        }
        // 最后讓組數(shù)為1再排序一次
        shell(array,1);
    }
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            // 默認每組內(nèi)第一個數(shù)據(jù)都是有序的，
            // 從每組的第二個數(shù)據(jù)開始進行直接插入排序
            // i++即是跳到下一組，
            // 每組排序一個數(shù)，然后跳到下一組，如此循環(huán)。
            int tmp = array[i];
            int j = i - gap;
            
            // 跳躍式的組內(nèi)直接插入排序
            for (; j >= 0 ; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
}

三、性能分析

希爾排序的特性總結(jié)：
希爾排序是對直接插入排序的優(yōu)化。直接插入排序的特定就是數(shù)據(jù)越有序，速度越快。

當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。


時間復(fù)雜度：
希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定： 有學(xué)者通過大量的試驗統(tǒng)計，得出結(jié)果為：O(n^1.25) - O(1.6*n^1.25)

空間復(fù)雜度：O(1)

穩(wěn)定性：
不相鄰的元素也會進行位置交換，是不穩(wěn)定。

四、七大排序算法性能對比

想學(xué)哪個點哪個
歸并排序講解
快速排序講解
直接插入排序講解
希爾排序講解
直接選擇排序講解
堆排序講解
冒泡排序講解文章來源地址http://www.zghlxwxcb.cn/news/detail-777882.html

到了這里，關(guān)于七大排序算法——希爾排序，通俗易懂的思路講解與圖解(完整Java代碼)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！