DIV CSS 佈局教程網

快速排序原理拆解與 Java 實作
編輯:JavaScript綜合知識     

快速排序大概是最常被拿來當排序預設值的演算法,JDK 裡的 Arrays.sort 對基本型別陣列採用的就是這套思路(現代版本是雙軸快排)。它之所以快,關鍵在於「幾乎不需要搬動資料」,全部都在原陣列上原地交換完成。

分治三步驟

Divide(分割):挑一個基準元 pivot,這裡取陣列第一個元素,然後做分區操作,讓左半邊都小於等於 pivot、右半邊都大於等於 pivot。

Conquer(解決):對左右兩個子陣列遞迴呼叫同一套分割流程。

Combine(合併):快排屬於原地排序(in-place sort),分割完成時資料已經各就各位,因此完全不需要合併步驟。這也是它比合併排序省記憶體的原因。

分區過程怎麼走

以《算法導論》的經典示意為例,初始化時取 pivot = 2(首元素),令 i = 1、j = i + 1 = 2(下標從 1 起算)。此時維持的循環不變式是:2 到 i 之間的元素都小於等於 pivot,i + 1 到 j 之間的元素都大於等於 pivot。

接著 j 從 2 掃到 n:若 a[j] 大於等於 pivot 就繼續往右;若小於 pivot,就把 a[j] 與 a[i+1] 交換,並將 i 加一。這樣不變式在每一步都成立。掃描結束後,還要把 a[i] 與首元素交換,把 pivot 放到它最終的正確位置。

聰明的讀者可能會想到另一種更直觀的做法:另開一個同大小陣列,比 pivot 小的丟左邊、大的丟右邊。時間複雜度同樣是 Θ(n),但空間複雜度直接翻倍,這正是原地排序的價值所在。

Java 實作

public class QuickSort {

    private static void quickSort(int[] array, int start, int end) {
        if (start < end) {
            int key = array[start];   // 基準元
            int i = start, j;
            for (j = start + 1; j <= end; j++) {
                if (array[j] < key) { // 比基準元小,換到左側並前移 i
                    int temp = array[j];
                    array[j] = array[i + 1];
                    array[i + 1] = temp;
                    i++;
                }
            }
            array[start] = array[i];  // 基準元歸位
            array[i] = key;

            quickSort(array, start, i - 1); // 遞迴處理左右子區間
            quickSort(array, i + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{11, 213, 134, 44, 77, 78, 23, 43};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println((i + 1) + "th:" + array[i]);
        }
    }
}

複雜度與實務提醒

平均時間複雜度 O(n log n),最壞情況 O(n²),多出現在陣列已排序或接近排序、而 pivot 又固定取首/尾元素的時候。實務上的解法是隨機選 pivot 或改用三數取中,並在子區間夠小時(例如長度小於 10)遞迴改用插入排序,這正是多數標準函式庫的實作策略。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved