時間複雜度為O(nlogn)的排序演算法

• 2020 年 7 月 21 日
• 筆記
• 數據結構, 數據結構與演算法

時間複雜度為O(nlogn)的排序演算法（歸併排序、快速排序）,比時間複雜度O(n²)的排序演算法更適合大規模數據排序。

歸併排序

歸併排序的核心思想

採用「分治思想」，將要排序的數組從中間分成前後兩個部分，然後對前後兩個部分分別進行排序，再將排序好的兩部分合併在一起，這樣數組就有序了。

分治是一種解決問題的思想，遞歸是一種編程技巧，使用遞歸的技巧就是，先找到遞歸公式和終止條件，然後將遞歸公式翻譯成遞歸程式碼。

歸併排序的遞推公式和終止條件：

//遞歸公式
merge_sort(p...r) = mege(merge_sort(p...q),merge_sort(q+1,r));

//終止條件
p >= r,不再繼續分解

歸併排序程式碼

public class MergeSort {

    public static void main(String[] args) {
        int[] a = {4, 3, 2, 1, 6, 5};
        mergeSort(a,0,a.length - 1);
        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void mergeSort(int[] a, int p, int r) {
        //終止條件
        if (p >= r) return;

        int q = (r - p) / 2 + p;
        //遞歸公式
        mergeSort(a, 0, q);
        mergeSort(a, q + 1, r);

        //到這裡遞歸結束，可以假設[0,q],[q + 1,r]已經排好序了
        merge(a, p, q, r);

    }

    private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int k = 0;
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        //判斷哪個子數字中有數據，判斷依據必須是 <=
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }

        //將剩餘數據拷貝到臨時數組temp中
        while (start <= end) {
            temp[k++] = a[start++];
        }

        //將temp數組中數據[0,r-p]，拷貝至a數組中原來位置
        //可以直接使用數組複製函數
        for (int n = 0; n <= r - p; n++) {
            a[p + n] = temp[n];
        }
    }
}

優化

可以利用哨兵節點對merge方法進行優化，將數組分配兩部分，並將Integer.MAX_VALUE添加到每個數組的最後一位，就可以一次性將兩個數組中數據全部比較完，不會剩餘數據

//優化merge程式碼
private static void mergeBySentry(int[] a, int p, int q, int r) {
    int[] leftArr = new int[q - p + 2];
    int[] rightArr = new int[r - q + 1];

    for (int i = 0; i <= q - p; i++) {
        leftArr[i] = a[p + i];
    }
    leftArr[q - p + 1] = Integer.MAX_VALUE;

    for (int i = 0; i < r - q; i++) {
        rightArr[i] = a[q + i + 1];
    }
    rightArr[r - q] = Integer.MAX_VALUE;


    int i = 0;
    int j = 0;
    int k = p;
    while (k <= r) {
        if (leftArr[i] <= rightArr[j]) {
            a[k++] = leftArr[i++];
        } else {
            a[k++] = rightArr[j++];
        }
    }
}

穩定性

歸併排序是穩定的排序演算法，是否穩定取決於合併merge方法，當兩個數組有相同數據合併時，可以先將左邊的數據先存入temp中，這樣就可以保證穩定性

時間複雜度

最好情況、最壞情況，還是平均情況，時間複雜度都是 O(nlogn)。推導過程待補充…

空間複雜度

歸併排序不是原地排序演算法。

遞歸程式碼的空間複雜度並不能像時間複雜度那樣累加。剛剛我們忘記了最重要的一點，那就是，儘管每次合併操作都需要申請額外的記憶體空間，但在合併完成之後，臨時開闢的記憶體空間就被釋放掉了。在任意時刻，CPU 只會有一個函數在執行，也就只會有一個臨時的記憶體空間在使用。臨時記憶體空間最大也不會超過 n 個數據的大小，所以空間複雜度是 O(n)

快速排序

快速排序核心思想

對數組p到r進行排序，從數組中從中取出一個數據作為pivot（分區點），將小於pivot的放在左邊，大於pivot的放在右邊，之後利用分治、遞歸思想，再對左右兩邊的數據進行排序，直到區間縮小為1，說明數據有序了

遞歸公式和終止條件

//遞歸公式
quick_sort(p...r) = quick_sort(p...q) + quick_sort(q + 1 ... r)  
    
//終止條件
p >= r

快速排序程式碼

public static void quickSort(int[] a, int n){
    quickSortInternally(a,0,n - 1);
}

private static void quickSortInternally(int[] a,int p, int r){
    if (p >= r) return;

    int q = partition(a, p, r);
    quickSortInternally(a,p,q - 1);
    quickSortInternally(a,q + 1,r);
}

//p:起始位置，r:終止位置
private static int partition(int[] a, int p, int r) {
    //取出中間點
    int pivot = a[r];

    //i、j為雙指針，i始終指向大於中間點的第一個元素，j不斷遍曆數組，最終指向最後一個元素即中間點
    int i = p;
    //比較從p開始，到r-1結束
    for(int j = p; j < r; ++j) {
        //如果小於中間點
        if (a[j] < pivot) {
            if (i == j) {
                //如果i和j相等，說明之前沒有大於中間點的元素，i和j都加1
                // j在進行下一輪循環的時候會自動加1，所以在這裡只加i
                ++i;
            } else {
                //如果不相等，說明i已經指向第一個大於中間點的元素
                // 需要將小於中間的的a[j]與a[i]交換位置，然後都加1
                int tmp = a[i];
                a[i++] = a[j];
                a[j] = tmp;
            }
        }
    }

    //循環結束，i指向大於中間點a[r]的第一個元素
    //將a[i]與a[r]交換位置
    int tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;

    System.out.println("i=" + i);
    //返回交換後中間點坐標位置
    return i;
}

性能分析

快速排序是原地、不穩定的排序演算法，時間複雜度在大部分情況下的時間複雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n²)

原地：空間複雜度為O(1)，不需要佔用額外存儲空間

不穩定：因為分區的過程涉及交換操作，如果數組中有兩個相同的元素，比如序列 6，8，7，6，3，5，9，4，在經過第一次分區操作之後，兩個 6 的相對先後順序就會改變。所以，快速排序並不是一個穩定的排序演算法

時間複雜度：待補充

思考

O(n) 時間複雜度內求無序數組中的第 K 大元素。比如，4， 2， 5， 12， 3 這樣一組數據，第 3 大元素就是 4。

思路：

• 選擇數組A[0,n-1]的最後一個元素A[n-1]作為中間點pivot

• 對數組A[0,n-1]原地分區，分為[0,p-1],[p],[p+1,n-1],此時[0,p-1]這個分區中雖然可能無序，但是全部是比中間點小的元素，所以[p]為這群數中的第p+1大元素（下標為p，所以共有p+1個元素，應該是p+1大）

• 比較p+1和K，如果p+1 = K，說明A[p]就是求解元素，如果K > p+1，說明求解元素出現在A[p+1,n-1]中，則按照上面方法遞歸對A[p+1,n-1]進行分去查找，同理，如果K < p+1，則對A[0,p-1]進行分區查找

時間複雜度：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)。

笨方法：每次取數組中的最小值，將其移動到數組的最前面，然後在剩下的數組中繼續找最小值，以此類推，執行 K 次，也可以找到第K大元素。但這種方法的時間複雜度為O(K*n),在K值比較小時，時間複雜度為O(n),當K為n/2或n時，時間複雜度就為O(n²)了

思考2

現在你有 10 個介面訪問日誌文件，每個日誌文件大小約 300MB，每個文件里的日誌都是按照時間戳從小到大排序的。你希望將這 10 個較小的日誌文件，合併為 1 個日誌文件，合併之後的日誌仍然按照時間戳從小到大排列。如果處理上述排序任務的機器記憶體只有 1GB，你有什麼好的解決思路，能「快速」地將這 10 個日誌文件合併嗎