C++ 快速排序算法实现详解

#include <iostream>
#include <vector>

using namespace std;

void quicksort(vector<int>& nums, int left, int right) {
    if (left >= right) return;

    int pivot = nums[left]; // 以第一个数为基准
    int i = left + 1, j = right;

    while (i <= j) {
        while (i <= j && nums[i] < pivot) i++; // 从左边找到第一个大于等于pivot的数
        while (i <= j && nums[j] > pivot) j--; // 从右边找到第一个小于等于pivot的数
        if (i <= j) {
            swap(nums[i], nums[j]); // 交换这两个数
            i++;
            j--;
        }
    }

    swap(nums[left], nums[j]); // 将pivot放到正确的位置

    quicksort(nums, left, j - 1); // 分治
    quicksort(nums, j + 1, right);
}

int main() {
    vector<int> nums = {10, 7, 8, 9, 1, 5};
    quicksort(nums, 0, nums.size() - 1);
    for (int num : nums) {
        cout << num << ' '; // 使用单引号
    }
    cout << endl;
    return 0;
}

输出：1 5 7 8 9 10