排序算法二：歸并排序與快速排序

文章目錄

• 比較兩種排序方法
• 比較排序的時間複雜度下限
• 一、歸并排序
• 二、快速排序

比較兩種排序方法

排序方法	時間複雜度	額外空間複雜度	是否穩定
歸并排序（Merge Sort）	O ( n l o g n ) O(nlogn) O(nlogn)	T ( n ) T(n) T(n)	是
快速排序（Quick Sort）	O ( n l o g n ) O(nlogn) O(nlogn)	T ( 1 ) T(1) T(1)	否

比較排序的時間複雜度下限

所有比較排序如：歸并排序、快速排序、堆排序、插入排序等基于兩兩比較數組内元素的排序算法的時間複雜度下限都是 O ( l o g ( N ! ) ) O(log(N!)) O(log(N!)) ~ O ( N l o g N ) O(NlogN) O(NlogN)

證明：使用二叉樹表示所有的比較，樹中的葉子節點表示排序完成，内部節點表示一個比較操作。假設該數組有N個元素，則該數組有N!種排列方式即二叉樹有N!個葉子節點。

從一個根節點到一個葉子節點的路徑長度是某種輸入下算法進行比較的次數，也就是算法比較次數的上限

高度為h的二叉樹最多擁有 2 h 2^h 2h個葉節點

是以，任意一棵基于比較的排序算法對應着一棵高度為h的比較樹，其中 N ! ≤ 葉 子 節 點 的 數 量 ≤ 2 h N! \leq {葉子節點的數量} \leq 2^h N!≤葉子節點的數量≤2h

是以， h > l o g ( N ! ) h > log(N!) h>log(N!)， 而 l o g ( N ! ) log(N!) log(N!) ~ N l o g ( N ) Nlog(N) Nlog(N)

是以所有基于比較的排序算法的時間複雜度下限為 N l o g ( N ) Nlog(N) Nlog(N)

一、歸并排序

基本方法： 歸并排序使用分治方法（Divide and Conquer）主要基于歸并操作，即将兩個有序的數組合起來歸并成一個有序的數列。定義完歸并之後，我們可以自頂上下遞歸地将數組折成兩半分别排序并最終歸并。

歸并的具體操作：

使用一個額外數組，用于存儲原數組中的值，定義三個指針low、high、k分别指向額外數組中對應原先左邊數組和右邊數組的第一個元素和原數組的首位，并比較大小。

如果i指向的小，則拷貝其到k指向的位置，并且把low與k進一位。

如果j指向的小，則拷貝其到k指向的位置，并且把high進一位。

如果額外數組中的左邊數組用盡，則将右邊數組剩餘的位置依次添加到原數組中

如果額外數組中的右邊數組用盡，則将左邊數組剩餘的位置依次添加到原數組中

例如：merge([1, 4, 7, 2, 5, 10], 0, 2, 5)

原數組	額外數組	i	j	k
( 1, 4, 7, 2, 5, 10 )	( 1, 4, 7, 2, 5, 10 )	3
( 1, 4, 7, 2, 5, 10 )	( 1, 4, 7, 2, 5, 10 )	1	4	1
( 1, 2, 7, 2, 5, 10 )	( 1, 4, 7, 2, 5, 10 )	2	4	2
( 1, 2, 4, 2, 3, 6 )	( 1, 4, 7, 2, 5, 10 )	2	4	3
( 1, 2, 4, 5, 3, 6 )	( 1, 4, 7, 2, 5, 10 )	2	5	4
( 1, 2, 4, 5, 7, 6 )	( 1, 4, 7, 2, 5, 10 )	3	5	5
( 1, 2, 4, 5, 7, 10 )	(1, 4, 7, 2, 5, 10 )

注：原數組中粗體數字為k所指向的元素，額外數組中粗體的兩個數字分别為i和j所指向的元素

以下為歸并排序的Java代碼實作：

public static void merge(int[] arr, int low, int mid, int high){
        int[] temp = new int[arr.length];
        int i = low, j = mid+1;
        for (int k = low; k <= high; k++){
            temp[k] = arr[k];
        }
        int k = low;
        while (i <= mid && j<= high){
            if (temp[i] < temp[j]){
                arr[k++] = temp[i++];
            }
            else {
                arr[k++] = temp[j++];
            }
        }
        while (i <= mid){
            arr[k++] = temp[i++];
        }
        while (j <= high){
            arr[k++] = temp[j++];
        }
    }


    public static void mergeSort(int[] arr, int low, int high){
        if (low >= high){
            return;
        }
        int mid = low + (high - low)/2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
           

二、快速排序

基本方法： 快速排序使用了分治方法（Divide and Conquer）主要基于分割方法（Partition），即将一個數組根據一個元素（pivot）分成兩部分，左邊小于等于這個元素，右邊大于這個元素，并傳回這個元素的位置。

Partition的具體操作：

選擇一個元素作為pivot（這邊取子數組中的最後一位）。定義兩個個指針i和j，i初始為子數組首位-1，j初始為子數組首位

循環比較j指向的元素與pivot的大小直至j超出子數組範圍

如果j指向的元素小于pivot，則i進一位，并交換i與j指向的元素

j進一位

交換pivot與i+1指向的元素，并傳回i+1

以下為Partition的Java代碼實作：

public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static int partition(int[] arr, int low, int high){
        int pivot = arr[high];
        int i = low-1;
        for (int j = i+1; j < high-1; j++){
            if (arr[j] <= pivot){
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i+1, high);
        return i+1;
    }
           

例如： 對子數組( 3, 2, 1, 5, 4 )進行partition

子數組	i	j	pivot
( 3, 2, 1, 5, 4 )	-1	4
( 3, 2, 1, 5, 4 )	1	4
( 2, 3, 1, 5, 4 )	1	2	4
( 2, 1, 3, 5, 4 )	2	3	4
( 2, 1, 3, 4, 5 )	2	3	4

快速排序的具體操作： 先對數組進行partition得出pivot，再遞歸的排序pivot所分割出的左右兩個子數組即可

以下為快速排序的的Java代碼實作：

public static void quickSort(int[] arr, int low, int high){
        if (low < high){
            int p = partition(arr, low, high);
            quickSort(arr, low, p-1);
            quickSort(arr, p+1, high);
        }
    }