時間復(fù)雜度為O (nlogn)的排序算法簡述

歸并排序

歸并排序遵循分治的思想：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后合并這些子問題的解來建立原問題的解，歸并排序的步驟如下：

劃分：分解待排序的 n 個元素的序列成各具 n/2 個元素的兩個子序列，將長數(shù)組的排序問題轉(zhuǎn)換為短數(shù)組的排序問題，當(dāng)待排序的序列長度為 1 時，遞歸劃分結(jié)束

合并：合并兩個已排序的子序列得出已排序的最終結(jié)果

歸并排序的代碼實(shí)現(xiàn)如下：

    private void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 劃分
        int mid = left + right >> 1;
        sort(nums, left, mid);
        sort(nums, mid + 1, right);
        // 合并
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        // 輔助數(shù)組
        int[] temp = Arrays.copyOfRange(nums, left, right + 1);

        int leftBegin = 0, leftEnd = mid - left;
        int rightBegin = leftEnd + 1, rightEnd = right - left;
        for (int i = left; i <= right; i++) {
            if (leftBegin > leftEnd) {
                nums[i] = temp[rightBegin++];
            } else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
                nums[i] = temp[leftBegin++];
            } else {
                nums[i] = temp[rightBegin++];
            }
        }
    }

歸并排序最吸引人的性質(zhì)是它能保證將長度為 n 的數(shù)組排序所需的時間和 nlogn 成正比；它的主要缺點(diǎn)是所需的額外空間和 n 成正比。 算法特性：

空間復(fù)雜度：借助輔助數(shù)組實(shí)現(xiàn)合并，使用 O (n) 的額外空間；遞歸深度為 logn，使用 O (logn) 大小的棧幀空間。忽略低階部分，所以空間復(fù)雜度為 O (n)

非原地排序

穩(wěn)定排序

非自適應(yīng)排序

以上代碼是歸并排序常見的實(shí)現(xiàn)，下面我們來一起看看歸并排序的優(yōu)化策略：

將多次創(chuàng)建小數(shù)組的開銷轉(zhuǎn)換為只創(chuàng)建一次大數(shù)組

在上文實(shí)現(xiàn)中，我們在每次合并兩個有序數(shù)組時，即使是很小的數(shù)組，我們都會創(chuàng)建一個新的 temp [] 數(shù)組，這部分耗時是歸并排序運(yùn)行時間的主要部分。更好的解決方案是將 temp [] 數(shù)組定義成 sort () 方法的局部變量，并將它作為參數(shù)傳遞給 merge () 方法，實(shí)現(xiàn)如下：

    private void sort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }

        // 劃分
        int mid = left + right >> 1;
        sort(nums, left, mid, temp);
        sort(nums, mid + 1, right, temp);
        // 合并
        merge(nums, left, mid, right, temp);
    }

    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int l = left, r = mid + 1;
        for (int i = left; i <= right; i++) {
            if (l > mid) {
                nums[i] = temp[r++];
            } else if (r > right || temp[l] < temp[r]) {
                nums[i] = temp[l++];
            } else {
                nums[i] = temp[r++];
            }
        }
    }

當(dāng)數(shù)組有序時，跳過 merge () 方法 我們可以在執(zhí)行合并前添加判斷條件：如果nums[mid] <= nums[mid + 1]?時我們認(rèn)為數(shù)組已經(jīng)是有序的了，那么我們就跳過 merge () 方法。它不影響排序的遞歸調(diào)用，但是對任意有序的子數(shù)組算法的運(yùn)行時間就變成線性的了，代碼實(shí)現(xiàn)如下：

    private void sort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }

        // 劃分
        int mid = left + right >> 1;
        sort(nums, left, mid, temp);
        sort(nums, mid + 1, right, temp);
        // 合并
        if (nums[mid] > nums[mid + 1]) {
            merge(nums, left, mid, right, temp);
        }
    }

    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int l = left, r = mid + 1;
        for (int i = left; i <= right; i++) {
            if (l > mid) {
                nums[i] = temp[r++];
            } else if (r > right || temp[l] < temp[r]) {
                nums[i] = temp[l++];
            } else {
                nums[i] = temp[r++];
            }
        }
    }

對小規(guī)模子數(shù)組使用插入排序 對小規(guī)模數(shù)組進(jìn)行排序會使遞歸調(diào)用過于頻繁，而使用插入排序處理小規(guī)模子數(shù)組一般可以將歸并排序的運(yùn)行時間縮短 10% ~ 15%，代碼實(shí)現(xiàn)如下：

    /**
     * M 取值在 5 ~ 15 之間大多數(shù)情況下都能令人滿意
     */
    private final int M = 9;

    private void sort(int[] nums, int left, int right) {
        if (left + M >= right) {
            // 插入排序
            insertSort(nums);
            return;
        }

        // 劃分
        int mid = left + right >> 1;
        sort(nums, left, mid);
        sort(nums, mid + 1, right);
        // 合并
        merge(nums, left, mid, right);
    }

    /**
     * 插入排序
     */
    private void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i];

            int j = i - 1;
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j--];
            }
            nums[j + 1] = base;
        }
    }

    private void merge(int[] nums, int left, int mid, int right) {
        // 輔助數(shù)組
        int[] temp = Arrays.copyOfRange(nums, left, right + 1);

        int leftBegin = 0, leftEnd = mid - left;
        int rightBegin = leftEnd + 1, rightEnd = right - left;
        for (int i = left; i <= right; i++) {
            if (leftBegin > leftEnd) {
                nums[i] = temp[rightBegin++];
            } else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {
                nums[i] = temp[leftBegin++];
            } else {
                nums[i] = temp[rightBegin++];
            }
        }
    }

快速排序 快速排序也遵循分治的思想，它與歸并排序不同的是，快速排序是原地排序，而且快速排序會先排序當(dāng)前數(shù)組，再對子數(shù)組進(jìn)行排序，它的算法步驟如下：

哨兵劃分：選取數(shù)組中最左端元素為基準(zhǔn)數(shù)，將小于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)左邊，將大于基準(zhǔn)數(shù)的元素放在基準(zhǔn)數(shù)右邊

排序子數(shù)組：將哨兵劃分的索引作為劃分左右子數(shù)組的分界，分別對左右子數(shù)組進(jìn)行哨兵劃分和排序

快速排序的代碼實(shí)現(xiàn)如下：

private void sort(int[] nums, int left, int right) {

        if (left >= right) {
            return;
        }

        // 哨兵劃分
        int partition = partition(nums, left, right);

        // 分別排序兩個子數(shù)組
        sort(nums, left, partition - 1);
        sort(nums, partition + 1, right);
    }

    /**
     * 哨兵劃分
     */
    private int partition(int[] nums, int left, int right) {
        // 以 nums[left] 作為基準(zhǔn)數(shù)，并記錄基準(zhǔn)數(shù)索引
        int originIndex = left;
        int base = nums[left];

        while (left < right) {
            // 從右向左找小于基準(zhǔn)數(shù)的元素
            while (left < right && nums[right] >= base) {
                right--;
            }
            // 從左向右找大于基準(zhǔn)數(shù)的元素
            while (left < right && nums[left] <= base) {
                left++;
            }
            swap(nums, left, right);
        }
        // 將基準(zhǔn)數(shù)交換到兩子數(shù)組的分界線
        swap(nums, originIndex, left);

        return left;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }算法特性：

時間復(fù)雜度：平均時間復(fù)雜度為 O (nlogn)，最差時間復(fù)雜度為 O (n2)

空間復(fù)雜度：最差情況下，遞歸深度為 n，所以空間復(fù)雜度為 O (n)

原地排序

非穩(wěn)定排序

自適應(yīng)排序

歸并排序的時間復(fù)雜度一直是 O (nlogn)，而快速排序在最壞的情況下時間復(fù)雜度為 O (n2)，為什么歸并排序沒有快速排序應(yīng)用廣泛呢？ 答：因?yàn)闅w并排序是非原地排序，在合并階段需要借助非常量級的額外空間

快速排序有很多優(yōu)點(diǎn)，但是在哨兵劃分不平衡的情況下，算法的效率會比較低效。下面是對快速排序排序優(yōu)化的一些方法：

切換到插入排序

對于小數(shù)組，快速排序比插入排序慢，快速排序的 sort () 方法在長度為 1 的子數(shù)組中也會調(diào)用一次，所以，在排序小數(shù)組時切換到插入排序排序的效率會更高，如下：

    /**
     * M 取值在 5 ~ 15 之間大多數(shù)情況下都能令人滿意
     */
    private final int M = 9;

    public void sort(int[] nums, int left, int right) {
        // 小數(shù)組采用插入排序
        if (left + M >= right) {
            insertSort(nums);
            return;
        }

        int partition = partition(nums, left, right);
        sort(nums, left, partition - 1);
        sort(nums, partition + 1, right);
    }

    /**
     * 插入排序
     */
    private void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i];

            int j = i - 1;
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j--];
            }
            nums[j + 1] = base;
        }
    }

    private int partition(int[] nums, int left, int right) {
        int originIndex = left;
        int base = nums[left];

        while (left < right) {
            while (left < right && nums[right] >= base) {
                right--;
            }
            while (left < right && nums[left] <= base) {
                left++;
            }
            swap(nums, left, right);
        }
        swap(nums, left, originIndex);

        return left;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

基準(zhǔn)數(shù)優(yōu)化 如果數(shù)組為倒序的情況下，選擇最左端元素為基準(zhǔn)數(shù)，那么每次哨兵劃分會導(dǎo)致右數(shù)組長度為 0，進(jìn)而使快速排序的時間復(fù)雜度為 O (n2)，為了盡可能避免這種情況，我們可以對基準(zhǔn)數(shù)的選擇進(jìn)行優(yōu)化，采用三取樣切分的方法：選取數(shù)組最左端、中間和最右端這三個值的中位數(shù)為基準(zhǔn)數(shù)，這樣選擇的基準(zhǔn)數(shù)大概率不是區(qū)間的極值，時間復(fù)雜度為 O (n2) 的概率大大降低，代碼實(shí)現(xiàn)如下：

    public void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 基準(zhǔn)數(shù)優(yōu)化
        betterBase(nums, left, right);

        int partition = partition(nums, left, right);

        sort(nums, left, partition - 1);
        sort(nums, partition + 1, right);
    }

    /**
     * 基準(zhǔn)數(shù)優(yōu)化，將 left, mid, right 這幾個值中的中位數(shù)換到 left 的位置
     * 注意其中使用了異或運(yùn)算進(jìn)行條件判斷
     */
    private void betterBase(int[] nums, int left, int right) {
        int mid = left + right >> 1;

        if ((nums[mid] < nums[right]) ^ (nums[mid] < nums[left])) {
            swap(nums, left, mid);
        } else if ((nums[right] < nums[left]) ^ (nums[right] < nums[mid])) {
            swap(nums, left, right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int originIndex = left;
        int base = nums[left];

        while (left < right) {
            while (left < right && nums[right] >= base) {
                right--;
            }
            while (left < right && nums[left] <= base) {
                left++;
            }
            swap(nums, left, right);
        }
        swap(nums, originIndex, left);

        return left;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

三向切分 在數(shù)組有大量重復(fù)元素的情況下，快速排序的遞歸性會使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn)，而對這些數(shù)組進(jìn)行快速排序是沒有必要的，我們可以對它進(jìn)行優(yōu)化。 一個簡單的想法是將數(shù)組切分為三部分，分別對應(yīng)小于、等于和大于基準(zhǔn)數(shù)的數(shù)組，每次將其中 “小于” 和 “大于” 的數(shù)組進(jìn)行排序，那么最終也能得到排序的結(jié)果，這種策略下我們不會對等于基準(zhǔn)數(shù)的子數(shù)組進(jìn)行排序，提高了排序算法的效率，它的算法流程如下： 從左到右遍歷數(shù)組，維護(hù)指針 l 使得 [left, l - 1] 中的元素都小于基準(zhǔn)數(shù)，維護(hù)指針 r 使得 [r + 1, right] 中的元素都大于基準(zhǔn)數(shù)，維護(hù)指針 mid 使得 [l, mid - 1] 中的元素都等于基準(zhǔn)數(shù)，其中 [mid, r] 區(qū)間中的元素還未確定大小關(guān)系，圖示如下：

它的代碼實(shí)現(xiàn)如下：

    public void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 三向切分
        int l = left, mid = left + 1, r = right;
        int base = nums[l];
        while (mid <= r) {
            if (nums[mid] < base) {
                swap(nums, l++, mid++);
            } else if (nums[mid] > base) {
                swap(nums, mid, r--);
            } else {
                mid++;
            }
        }

        sort(nums, left, l - 1);
        sort(nums, r + 1, right);
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

這也是經(jīng)典的荷蘭國旗問題，因?yàn)檫@就好像用三種可能的主鍵值將數(shù)組排序一樣，這三種主鍵值對應(yīng)著荷蘭國旗上的三種顏色

審核編輯：黃飛