【算法 之快速排序 原理及案例】

快速排序（Quick Sort）

快速排序（Quick Sort）是一种非常高效的排序算法，它采用了分治（Divide and Conquer）的思想。快速排序的基本步骤是：

1. 选择一个基准元素（pivot）：通常选择序列的第一个或最后一个元素作为基准。
2. 划分（Partition）：通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小。
3. 递归（Recursion）：按上述方法递归地对两部分进行快速排序，直到整个序列有序。

以下是快速排序的 C++ 代码示例：

#include <iostream>  
#include <vector>  
  
// 划分函数  
int partition(std::vector<int>& nums, int low, int high) {  
    int pivot = nums[high];    // 选择最右边的元素作为基准  
    int i = (low - 1);  // 指向小于基准元素的最后一个位置  
  
    for (int j = low; j <= high - 1; j++) {  
        // 如果当前元素小于或等于基准元素  
        if (nums[j] <= pivot) {  
            i++;    // 增加 i  
            std::swap(nums[i], nums[j]); // 交换  
        }  
    }  
    std::swap(nums[i + 1], nums[high]); // 将基准元素放到最终的位置  
    return (i + 1);  
}  
  
// 快速排序函数  
void quickSort(std::vector<int>& nums, int low, int high) {  
    if (low < high) {  
        // pi 是分区索引，nums[pi] 现在在正确的位置  
        int pi = partition(nums, low, high);  
  
        // 分别对基准元素前后两部分进行递归排序  
        quickSort(nums, low, pi - 1);  
        quickSort(nums, pi + 1, high);  
    }  
}  
  
// 测试  
int main() {  
    std::vector<int> nums = {10, 7, 8, 9, 1, 5};  
    int n = nums.size();  
    quickSort(nums, 0, n - 1);  
  
    std::cout << "Sorted array: \n";  
    for (int i = 0; i < n; i++)  
        std::cout << nums[i] << " ";  
    return 0;  
}

这段代码首先定义了一个 partition 函数，用于根据基准元素将数组划分为两部分。然后，quickSort 函数递归地调用 partition 函数，直到整个数组有序。在 main 函数中，我们创建了一个待排序的数组，并调用了 quickSort 函数进行排序。最后，我们打印出排序后的数组。