# 快速排序法 Quick Sort
## 簡介
這是快速排序法（Quick Sort），其時間複雜度為最佳 $O(n \log n)$，最差 $O(n^2)$，而平均情況下是 $O(n \log n)$。
## 運作原理
快速排序法的運作原理
快速排序是一種基於分治法的排序算法，它將一個陣列分成兩個子陣列，然後遞迴排序這些子陣列。基本思路是：

1.選擇基準元素（Pivot）：從陣列中選擇一個元素作為基準元素。

2.分區操作：將陣列重新排列，使得所有比基準元素小的元素在它的左邊，所有比基準元素大的元素在它的右邊。

3.遞迴：對基準元素左右的子陣列進行相同的操作，直到陣列變得有序。
## 時間複雜度
* 最佳情況：每次分區操作都將陣列平均分割，這時的時間複雜度為 $O(n \log n)$。

* 最差情況：如果每次選擇的基準元素是當前子陣列的最大或最小元素（例如，已排序的陣列），則每次分區後的兩個子陣列分割不均，時間複雜度會退化為 $O(n^2)$。

* 平均情況：隨機選擇基準元素能夠大幅減少最差情況的發生機率，因此平均時間複雜度為 $O(n \log n)$。
## 優缺點
* 優點：
* 平均情況下，快速排序表現非常好，且時間複雜度為 $O(n \log n)$。
* 在內部排序中，它是原地排序的，因此不需要額外的空間，空間複雜度是 $O(\log n)$（遞迴所需的空間）。

* 缺點：
* 最差情況是 $O(n^2)$，但這可以通過隨機選擇基準元素來減少發生的機會。
* 快速排序是不穩定的排序，即相同值的元素可能會改變相對順序。
## Code

mt19937 mt;

int partition(vector<int> &v, int front, int end) {
    uniform_int_distribution<int> dis(front, end);
    int rnd = dis(mt), k = v[rnd];
    swap(v[rnd], v[end]);
    int p = front;
    for(; front < end; front++) {
        if(v[front] < k) swap(v[front], v[p++]);
    }
    swap(v[p], v[end]);
    return p;
}

void quicksort(vector<int> &v, int front, int end) {
    if(front < end) {
        int pivot = partition(v, front, end);
        quicksort(v, front, pivot - 1);
        quicksort(v, pivot + 1, end);
    }
}

// quicksort(v, 0, v.size() - 1)