快速排序實現的C++函數模板

快速排序（Quicksort）算法是一種常用的基於比較的排序算法，其時間複雜度為O(nlogn)。在該算法中，通過選擇樞紐元素將待排序數組分割成兩個子序列，其中一個子序列的所有元素都小於樞紐元素，另外一個子序列的所有元素都大於等於樞紐元素。然後遞歸的排序這兩個子序列。

下面是快速排序實現的C++函數模板：

template <typename T>
void quick_sort(vector<T>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    T pivot = arr[(left + right) / 2];
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

一、快速排序的原理和算法流程

在快速排序算法中，通過選擇一個樞紐元素，將待排序的數組分割成兩個子序列。樞紐元素選取的方式有多種，例如可以選擇第一個元素、最後一個元素或者中間的元素。通常情況下，我們選擇中間的元素作為樞紐元素，因為這樣可以避免最壞時間複雜度的出現。

算法流程如下：

• 1. 選擇一個樞紐元素pivot，一般取數組中間的元素
• 2. 將待排序數組分成兩個子序列，一個序列中所有元素都小於pivot，另一個序列中所有元素都大於等於pivot
• 3. 對這兩個子序列遞歸執行第1步和第2步操作

二、實現細節和優化

快速排序是一種高效的排序算法，但是在實際使用中，存在一些需要注意的實現細節和優化點，下面列舉一些：

• 1. 在樞紐元素的選擇上，可以採用三數取中的方式，即選擇左、中、右三個元素的中位數作為樞紐元素。這種方式可以避免在排序的過程中出現最壞情況。
• 2. 在排序前，可以對待排序數組進行一次隨機打亂，這樣可以避免在數組已經有序或者近乎有序的情況下出現最壞情況。
• 3. 迭代實現快速排序比遞歸實現快速排序更高效，因為在遞歸實現中需要調用函數和壓棧，需要耗費額外的時間和空間。
• 4. 對於小規模的數組，使用插入排序或者選擇排序可以提高快速排序的效率。
• 5. 在實際使用中，可以使用STL中的sort函數替代手寫的快速排序，這樣可以避免一些實現細節和錯誤。

三、快速排序的應用場景

快速排序是一種常見的排序算法，廣泛應用於各種軟件系統中，例如：

• 1. 數據庫系統中對數據進行排序
• 2. 操作系統中進行進程/線程調度
• 3. 計算機網絡中對數據進行排序
• 4. 一些組合優化問題中的求解方法

四、代碼示例

下面是使用上述快速排序函數模板的示例，對一個整數數組進行排序：

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void quick_sort(vector<T>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    T pivot = arr[(left + right) / 2];
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

int main() {
    vector<int> arr = {3, 7, 4, 5, 2, 1, 9, 8, 6};
    quick_sort(arr, 0, arr.size() - 1);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}