C++实现快速排序(Quicksort)算法

快速排序(Quicksort)算法是一种常见的排序算法，具有快速、高效、稳定性好等特点，广泛应用于各种工程实践中。

快速排序的基本思想

快速排序的基本思想是：选取一个基准值(pivot)，将待排序序列划分成左右两个子序列，左边的子序列中所有元素都不大于基准值，右边的子序列中所有元素都不小于基准值，然后对左右两个子序列进行递归排序，最终得到有序序列。

C++实现快速排序算法

下面是C++实现快速排序算法的完整代码：

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i+1], nums[right]);
    return i+1;
}

void quicksort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int p = partition(nums, left, right);
        quicksort(nums, left, p-1);
        quicksort(nums, p+1, right);
    }
}

void print(vector<int>& nums) {
    for (auto num : nums)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> nums = {3, 9, 4, 2, 5, 1, 7, 6, 8};
    quicksort(nums, 0, nums.size()-1);
    print(nums);

    return 0;
}

上面的代码实现了快速排序算法的核心部分：partition函数和quicksort函数。其中，partition函数是划分函数，用来将待排序序列划分成左右两个子序列；quicksort函数是递归排序函数，用来对左右两个子序列进行递归排序。

示例说明

下面给出两个示例来说明快速排序算法的实现过程。

示例1：

原始序列：[3, 9, 4, 2, 5, 1, 7, 6, 8]

第一次划分结果：[3, 4, 2, 1, 6, 8, 9, 7, 5]

第二次划分结果：[1, 2, 3, 4, 6, 8, 9, 7, 5]

第三次划分结果：[1, 2, 3, 4, 5, 6, 8, 9, 7]

第四次划分结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]

经过四次划分后得到有序序列。可以看到，快速排序算法具有快速、高效、稳定性好等特点。

示例2：

原始序列：[2, 1, 4, 3, 6, 5, 8, 7, 9]

第一次划分结果：[1, 2, 3, 4, 6, 5, 8, 7, 9]

第二次划分结果：[1, 2, 3, 4, 6, 5, 8, 7, 9]

第三次划分结果：[1, 2, 3, 4, 5, 6, 8, 7, 9]

第四次划分结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]

经过四次划分后得到有序序列。可以看到，快速排序算法对于不同的数据集都具有高效的排序能力。

总结

快速排序算法是一种经典的排序算法，实现简单，运行速度快，效率高，是大多数应用领域中使用最广的排序算法之一。对于快速排序算法的实现过程有了深刻的理解，可以为我们在实践中使用快速排序算法提供有力的支持。