常用算法介绍--＞快速排序

#include <iostream>
#include <vector>
// 交换两个元素的值
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
// 分区函数，将小于pivot的元素放在左边，大于等于pivot的元素放在右边
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选取最后一个元素作为pivot
    int i = low - 1; // 记录分区位置
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 将pivot放在正确的位置上
    return i + 1; // 返回分区位置
}
// 快速排序函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high); // 获取分区位置
        quickSort(arr, low, partitionIndex - 1); // 对左半部分递归排序
        quickSort(arr, partitionIndex + 1, high); // 对右半部分递归排序
    }
}
// 打印数组元素
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    std::cout << std::endl;
}
int main() {
    std::vector<int> arr = {5, 9, 3, 1, 8, 6, 2, 7};
    std::cout << "Original array: ";
    printArray(arr);
    quickSort(arr, 0, arr.size() - 1);
    std::cout << "Sorted array: ";
    printArray(arr);
    return 0;
}