快速排序

原理思想
• 分治思想：快速排序遵循分治策略，将一个大问题（对整个数组排序）分解成多个小问题（对划分后的子数组排序）。先选择数组中的一个元素作为“基准”元素，比如常选第一个或最后一个元素。
• 划分操作：通过双指针法（左右指针），从数组两端开始扫描，将小于基准的元素移到左边，大于基准的元素移到右边，最终确定基准元素的正确位置，使数组以基准为界分为左右两部分，左边元素都小于等于它，右边元素都大于等于它。
代码实现要点
• 划分函数：
    传入待排序数组、起始索引与结束索引，函数内通过指针移动交换元素来完成划分，返回基准元素最终位置索引，便于后续递归调用。
    需注意指针移动条件及元素交换逻辑，避免越界等错误。
• 递归调用：
    基于划分后基准元素的位置，分别对左右子数组进行递归排序，递归的边界条件通常是子数组长度大于1（即起始索引小于结束索引）。
    合理设置递归终止情况，防止无限递归。
代码：

#include
#include
using namespace std;

// 交换两个元素的函数
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 划分函数，选择一个基准元素，将数组划分为两部分
int partition(vector& arr, int low, int high) {
    int pivot = arr[high];  // 通常选择最后一个元素作为基准
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序递归函数
void quickSort(vector& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 打印数组元素的函数，方便查看排序结果
void printArray(const vector& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector arr = { 12, 11, 13, 5, 6 };
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组: ";
    printArray(arr);
    return 0;
}