演算法筆記：Qsort

quick sort 的演算法簡直是我最熟悉的陌生人，競賽、上課那幾個時候跟他都還挺好的，但好像只要一陣子不寫(其實現在除了考試或刻意練習外也不太容易用到了，內建的 sort 很好用)，就忘得要從 google 搜尋開始，乾脆自己寫筆記吧，看能不能記住點。

 

什麼是 Quick sort？ 

一種分而治之（Divide and Conquer）排序的演算法，排序 n 個項目要 O(n log⁡ n) 的時間複雜度，在最壞狀況下則需要 O(n*n)，常用程度和必考程度都很高的一種演算法。

核心架構與實作

1. 選定一個基準值(pivot)
2. 將所有比 pivot 小的值擺在 pivot 之前、比 pivot 大的擺在後面
3. 到剛剛分類完的子集合中遞迴執行上面的步驟

 如果上面看完還不能理解，可以在 youtube 搜尋 quick sort，觀察整個排序過程 (這邊找了一個我自己看得懂的)。

 

程式實作(C++)

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 取最後一個元素當 pivot
    int i = low - 1;       // i 代表小於 pivot 的最後位置

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 把 pivot 放到正確位置
    return i + 1;
}

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1); // 排左半部
        quickSort(arr, pi + 1, high); // 排右半部
    }
}