做法

  • Quick Sort 與 Merge Sort 雖然利用同樣的概念，但是作法上差異很大，它會先從陣列中選擇一個「樞紐」（pivot），然後將所有小於樞紐的值都移到它的左邊、將所有大於樞紐的值都移到它的右邊。移動的過程我們並沒有去做排序，我們只是先將它們移到某一邊。ps. 結束時，只有 pivot 會在它最後正確的位置上（也就是只有樞紐是在排好序的位置）。
  • 當樞紐完成以後，我們對左半部分再次進行同樣的處理（找到 pivot、移動位置），再處理右半部分。

時間複雜度分析：

  1. 最壞情況(Worst Case): O(n²)
    • 當基準值總是選到最大或最小元素時
    • 當數組已經排序或逆序時
    • 分割非常不平衡時
  2. 最好情況(Best Case): O(n log n)
    • 當每次分割都能將數組平均分成兩半時
    • 遞迴樹的深度為 log n
    • 每層需要 O(n) 的操作
  3. 平均情況(Average Case): O(n log n)
    • 在隨機數據下，通常能達到這個效率
    • 這也是實際應用中最常見的情況
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class QuickSort
{
    static void QuickSortArray(int[] arr, int left, int right)
    {
        if (left < right)
        {
            // 取得分割點
            int pivotIndex = Partition(arr, left, right);

            // 遞迴排序分割點左側的子數組
            QuickSortArray(arr, left, pivotIndex - 1);
            
            // 遞迴排序分割點右側的子數組
            QuickSortArray(arr, pivotIndex + 1, right);
        }
    }

    static int Partition(int[] arr, int left, int right)
    {
        // 選擇最右邊的元素作為基準值
        int pivot = arr[right];
        
        // i 表示小於基準值的元素的最後位置
        int i = left - 1;

        // 遍歷從 left 到 right-1 的元素
        for (int j = left; j < right; j++)
        {
            // 如果當前元素小於基準值
            if (arr[j] < pivot)
            {
                i++;
                // 交換元素
                Swap(arr, i, j);
            }
        }

        // 將基準值放到正確的位置
        Swap(arr, i + 1, right);
        return i + 1;
    }

    static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}