重學數據結構和算法(五)之歸併排序、快速排序

最近學習了極客時間的《數據結構與算法之美》很有收穫,記錄總結一下。
歡迎學習老師的專欄:數據結構與算法之美
代碼地址://github.com/peiniwan/Arithmetic

歸併排序(Merge Sort)

冒泡排序、插入排序、選擇排序這三種排序算法,它們的時間複雜度都是 O(n2),比較高,適合小規模數據的排序。歸併排序和快速排序的時間複雜度為 O(nlogn) 。這兩種排序算法適合大規模的數據排序

穩定,但是,歸併排序並沒有像快排那樣,應用廣泛,這是為什麼呢?因為它有一個致命的「弱點」,那就是歸併排序不是原地排序算法。
這是因為歸併排序的合併函數,在合併兩個有序數組為一個有序數組時,需要藉助額外的存儲空間。

歸併排序的原理:分治法

歸併排序和快速排序都用到了分治思想,非常巧妙。我們可以借鑒這個思想,來解決非排序的問題,比如:如何在 O(n) 的時間複雜度內查找一個無序數組中的第 K 大元素?

如果要排序一個數組,我們先把數組從中間分成前後兩部分,然後對前後兩部分分別排序,再將排好序的兩部分合併在一起,這樣整個數組就都有序了。

歸併排序使用的就是分治思想。分治,顧名思義,就是分而治之,將一個大問題分解成小的子問題來解決。小的子問題解決了,大問題也就解決了。
分治法的基本思想是:將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題,然後將這些子問題的解組合為原問題的解。

分治思想跟我們前面講的遞歸思想很像。是的,分治算法一般都是用遞歸來實現的。分治是一種解決問題的處理思想,遞歸是一種編程技巧,這兩者並不衝突

如何用遞歸代碼來實現歸併排序

寫遞歸代碼的技巧就是,分析得出遞推公式,然後找到終止條件,最後將遞推公式翻譯成遞歸代碼。所以,要想寫出歸併排序的代碼,我們先寫出歸併排序的遞推公式。

遞推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

終止條件:
p >= r 不用再繼續分解

merge_sort(p…r) 表示,給下標從 p 到 r 之間的數組排序。我們將這個排序問題轉化為了兩個子問題,merge_sort(p…q) 和 merge_sort(q+1…r),其中下標 q 等於 p 和 r 的中間位置,也就是 (p+r)/2。當下標從 p 到 q 和從 q+1 到 r 這兩個子數組都排好序之後,我們再將兩個有序的子數組合併在一起,這樣下標從 p 到 r 之間的數據就也排好序了。

public class MergeSort {
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(a, left, middle);//左邊歸併排序,使得左子序列有序
            mergeSort(a, middle + 1, right);//右邊歸併排序,使得右子序列有序
            merge(a, left, middle, right);//將兩個有序子數組合併操作
        }
    }

    private void merge(int[] a, int left, int middle, int right) {//left0,mid0,right1
        //在排序前,先建好一個長度等於原數組長度的臨時數組,避免遞歸中頻繁開闢空間
        int[] tmpArray = new int[a.length];
        int rightStart = middle + 1;//右序列指針
        int leftStart = left;//左序列指針
        int temp = left;//臨時數組指針
        //比較兩個小數組相應下標位置的數組大小,小的先放進新數組
        while (left <= middle && rightStart <= right) {
            if (a[left] <= a[rightStart]) {
                //相當於tmpArray[third]=a[left];third++;left++三步合一步
                tmpArray[temp++] = a[left++];
            } else {
                tmpArray[temp++] = a[rightStart++];
            }
        }
        //如果左邊還有數據需要拷貝,把左邊數組剩下的拷貝到新數組
        while (left <= middle) {
            tmpArray[temp++] = a[left++];
        }
        //如果右邊還有數據......
        while (rightStart <= right) {
            tmpArray[temp++] = a[rightStart++];
        }
        //將temp中的元素全部拷貝到原數組中
        while (leftStart <= right) {
            a[leftStart] = tmpArray[leftStart++];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = new int[]{9, 7, 6, 5, 4, 3, 2, 1};
        mergeSort.mergeSort(a, 0, a.length - 1);
        for (int n : a) {
            System.out.print(" " + n);
        }
    }
}

快速排序(Quicksort)

快排是一種原地、不穩定的排序算法。
快排利用的也是分治思想。乍看起來,它有點像歸併排序,但是思路其實完全不一樣。我們待會會講兩者的區別。現在,我們先來看下快排的核心思想。
基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。利用分治法可將快速排序的分為三步:

  1. 在數據集之中,選擇一個元素作為」基準」(pivot)。
  2. 所有小於」基準」的元素,都移到」基準」的左邊;所有大於」基準」的元素,都移到」基準」的右邊。這個操作稱為分區 (partition) 操作,分區操作結束後,基準元素所處的位置就是最終排序後它的位置。
  3. 對」基準」左邊和右邊的兩個子集,不斷重複第一步和第二步,直到所有子集只剩下一個元素為止。

快速排序和歸併排序對比
歸併排序的處理過程是由下到上的,先處理子問題,然後再合併。而快排正好相反,它的處理過程是由上到下的,先分區,然後再處理子問題。歸併排序雖然是穩定的、時間複雜度為 O(nlogn) 的排序算法,但是它是非原地排序算法。我們前面講過,歸併之所以是非原地排序算法,主要原因是合併函數無法在原地執行。快速排序通過設計巧妙的原地分區函數,可以實現原地排序,解決了歸併排序佔用太多內存的問題。

代碼實現快速排序

public class QuickSort {

    public void quick(int[] a) {
        if (a.length > 0) {
            quickSort(a, 0, a.length - 1);
        }
    }

    /**
     * 快速排序
     * @param a
     * @param low  低位
     * @param high 高位
     */
    private void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int middle = getMiddle(a, low, high);
            //遞歸排比第一個基數小的數和大的數
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    /**
     *
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int temp = a[low];//基準元素
        while (low < high) {//第二次3,9
            while (low < high && a[high] >= temp) {
                high--;
            }
            a[low] = a[high];//將比基數小的數放到基數前面///用個數字想一下就明白了
            while (low < high && a[low] <= temp) {
                low++;
            }
            a[high] = a[low];//將比基數大的數放到基數後面
        }
        a[low] = temp;//插入到排序後正確的位置,low就是基數應該在的位置
        return low;
    }
}

O(n) 時間複雜度內求無序數組中的第 K 大元素

快排核心思想就是分治和分區,我們可以利用分區的思想,來解答開篇的問題:O(n) 時間複雜度內求無序數組中的第 K 大元素。比如,4, 2, 5, 12, 3 這樣一組數據,第 3 大元素就是 4。
我們選擇數組區間 A[0…n-1] 的最後一個元素 A[n-1] 作為 pivot,對數組 A[0…n-1] 原地分區,這樣數組就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。

如果 p+1=K,那 A[p] 就是要求解的元素;如果 K>p+1, 說明第 K 大元素出現在 A[p+1…n-1] 區間,我們再按照上面的思路遞歸地在 A[p+1…n-1] 這個區間內查找。同理,如果 K<p+1,那我們就在 A[0…p-1] 區間查找。

int kthLargest = leetCode.findKthLargest(new int[]{4, 2, 5, 12, 3}, 3);
//倒數
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = len - 1;
        int pivot = 0;
        while (len - k != (pivot = partition(nums, left, right))) {
        //4所在的問題就是2,那就找到了
        //第k大應該在第K位,找每個數字應該在的位置,正好第0個4就是第K位,就找到了
            if (pivot < len - k) {//在後面
                left = pivot + 1;
                right = len - 1;
            } else {
                left = 0;
                right = pivot - 1;
            }
        }
        return nums[pivot];
    }
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
}

為什麼上述解決思路的時間複雜度是 O(n)?
第一次分區查找,我們需要對大小為 n 的數組執行分區操作,需要遍歷 n 個元素。第二次分區查找,我們只需要對大小為 n/2 的數組執行分區操作,需要遍歷 n/2 個元素。依次類推,分區遍曆元素的個數分別為、n/2、n/4、n/8、n/16.……直到區間縮小為 1。
如果我們把每次分區遍歷的元素個數加起來,就是:n+n/2+n/4+n/8+…+1。這是一個等比數列求和,最後的和等於 2n-1。所以,上述解決思路的時間複雜度就為 O(n)。