算法-排序-下（Sorting）

7.希爾排序（Shell Sort）

? 1959年由唐納德·希爾（Donald Shell）提出
? 希爾排序把序列看作是一個矩陣，分成 m 列群凶，逐列進行排序
m 從某個整數(shù)逐漸減為1
當(dāng) m 為1時沫浆，整個序列將完全有序

? 因此躯保，希爾排序也被稱為遞減增量排序（Diminishing Increment Sort）

? 矩陣的列數(shù)取決于步長序列（step sequence）
? 比如飞苇，如果步長序列為{1,5,19,41,109,...}，就代表依次分成109列收夸、41列坑匠、19列、5列卧惜、1列進行排序
? 不同的步長序列厘灼，執(zhí)行效率也不同

希爾排序 – 實例
? 希爾本人給出的步長序列是 n/(2^k)夹纫，比如 n為16時，步長序列是{1, 2, 4, 8}

? 分成8列進行排序

? 分成4列進行排序

? 分成2列進行排序

? 分成1列進行排序

? 不難看出來设凹，從8列變?yōu)?1列的過程中舰讹，逆序?qū)Φ臄?shù)量在逐漸減少
因此希爾排序底層一般使用插入排序?qū)γ恳涣羞M行排序，也很多資料認(rèn)為希爾排序是插入排序的改進版

希爾排序 – 實例

? 假設(shè)有11個元素闪朱，步長序列是{1, 2, 5}

? 假設(shè)元素在第 col 列月匣、第 row 行，步長（總列數(shù)）是 step
那么這個元素在數(shù)組中的索引是 col + row * step
比如 9 在排序前是第 2 列监透、第 0 行，那么它排序前的索引是 2 + 0 * 5 = 2
比如 4 在排序前是第 2 列航唆、 1 行胀蛮，那么它排序前的索引是 2 + 1 * 5 = 7
實現(xiàn)

@Override
    protected void sort() {
        List<Integer> stepSequence = shellSequence();
        for (Integer step : stepSequence) {
            //按照步長進行排序
            sort(step);
        }
    }
    /**
     * 分成step列進行排序
     */
    private void sort(int step) {
        // col : 第幾列，column的簡稱
        for (int col = 0; col < step; col++) {// 對第col列進行排序
            // col糯钙、col+step粪狼、col+2*step、col+3*step
            for (int begin = col + step; begin < arr.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /*
     * 獲取步長數(shù)組
     */
    private List<Integer> shellSequence(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = arr.length;
        while ((step = step >> 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }

? 最好情況是步長序列只有1任岸，且序列幾乎有序再榄，時間復(fù)雜度為 O(n)
? 空間復(fù)雜度為O(1)，屬于不穩(wěn)定排序
? 希爾本人給出的步長序列享潜，最壞情況時間復(fù)雜度是 O(n^2)

? 目前已知的最好的步長序列困鸥，最壞情況時間復(fù)雜度是 O(n^(4/3)) ，1986年由Robert Sedgewick提出

private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= arr.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

8.計數(shù)排序（Counting Sort）

? 之前學(xué)習(xí)的冒泡剑按、選擇疾就、插入、歸并艺蝴、快速猬腰、希爾、堆排序猜敢，都是基于比較的排序
平均時間復(fù)雜度目前最低是 O(nlogn)

? 計數(shù)排序姑荷、桶排序、基數(shù)排序缩擂，都不是基于比較的排序
它們是典型的用空間換時間鼠冕，在某些時候，平均時間復(fù)雜度可以比 O(nlogn) 更低

? 計數(shù)排序于1954年由Harold H. Seward提出胯盯，適合對一定范圍內(nèi)的整數(shù)進行排序

? 計數(shù)排序的核心思想
統(tǒng)計每個整數(shù)在序列中出現(xiàn)的次數(shù)供鸠，進而推導(dǎo)出每個整數(shù)在有序序列中的索引

計數(shù)排序 – 最簡單的實現(xiàn)

@Override
    protected void sort() {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //統(tǒng)計每個元素出現(xiàn)的次數(shù),counts的長度取決于arr中最大的元素
        int[] counts = new int[1 + max];
        for (int i = 0; i < arr.length; i++) {
            //arr[i]是作為counts的索引
            counts[arr[i]] ++;
        }
        //按照順序賦值
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            //counts[i]代表每個元素出現(xiàn)的次數(shù),索引i就是arr中的元素
            while (counts[i] -- > 0) {
                arr[index ++] = i;
            }
        }
    }

? 這個版本的實現(xiàn)存在以下問題
無法對負(fù)整數(shù)進行排序
極其浪費內(nèi)存空間
是個不穩(wěn)定的排序

計數(shù)排序 – 改進思路

...

    @Override
    protected void sort() {
        //獲取元素最大值
        int max = arr[0];
        //獲取元素最小值
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 開辟內(nèi)存空間，存儲次數(shù)
        int[] counts = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            //arr[i]-min是作為counts的索引
            counts[arr[i] - min]++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        //用于存放排序好的數(shù)組
        int[] output = new int[arr.length];
        for (int i = counts.length - 1; i >= 0; i--) {
            output[--counts[arr[i]-min]] = arr[I];
        }
        //重新賦值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

? 最好陨闹、最壞楞捂、平均時間復(fù)雜度：O(n + k)
? 空間復(fù)雜度：O(n + k)
? k 是整數(shù)的取值范圍
? 屬于穩(wěn)定排序

9.基數(shù)排序（Radix Sort）

? 基數(shù)排序非常適合用于整數(shù)排序（尤其是非負(fù)整數(shù)）薄坏，因此本課程只演示對非負(fù)整數(shù)進行基數(shù)排序
? 執(zhí)行流程：依次對個位數(shù)、十位數(shù)寨闹、百位數(shù)胶坠、千位數(shù)、萬位數(shù)...進行排序（從低位到高位）

? 個位數(shù)繁堡、十位數(shù)沈善、百位數(shù)的取范圍都是固定的0~9，可以使用計數(shù)排序?qū)λ鼈冞M行排序
? 思考：如果先對高位排序椭蹄，再對低位排序闻牡，是否可行？

    @Override
    protected void sort() {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 個位數(shù): array[i] / 1 % 10 = 3
        // 十位數(shù)：array[i] / 10 % 10 = 9
        // 百位數(shù)：array[i] / 100 % 10 = 5
        // 千位數(shù)：array[i] / 1000 % 10 = ...
        for (int divider = 1; divider <= max; divider *= 10) {
            countSort(divider);
        }
    }
    private void countSort(int divider) {
        // 開辟內(nèi)存空間绳矩，存儲次數(shù)
        int[] counts = new int[10];
        // 統(tǒng)計每個整數(shù)出現(xiàn)的次數(shù)
        for (int i = 0; i < arr.length; i++) {
            //arr[i]counts的索引
            counts[arr[i] / divider % 10]++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        // 從后往前遍歷元素罩润，將它放到有序數(shù)組中的合適位置
        int[] output = new int[arr.length];
        for (int i = counts.length - 1; i >= 0; i--) {
            output[--counts[arr[i] / divider % 10]] = arr[i];
        }
        //重新賦值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

? 最好、最壞翼馆、平均時間復(fù)雜度：O(d ? (n + k)) 割以，d 是最大值的位數(shù)，k 是進制应媚。屬于穩(wěn)定排序
? 空間復(fù)雜度：O(n + k)严沥，k 是進制

基數(shù)排序 – 另一種思路

10.桶排序（Bucket Sort）

? 執(zhí)行流程
① 創(chuàng)建一定數(shù)量的桶（比如用數(shù)組、鏈表作為桶）
② 按照一定的規(guī)則（不同類型的數(shù)據(jù)中姜，規(guī)則不同）消玄，將序列中的元素均勻分配到對應(yīng)的桶
③ 分別對每個桶進行單獨排序
④ 將所有非空桶的元素合并成有序序列

? 元素在桶中的索引
元素值 * 元素數(shù)量