C++算法竞赛基础语法-9

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出，基本思想是分治法（Divide and Conquer）策略，通过递归将一个大问题分解为若干个较小的子问题，然后合并这些子问题的解来解决原始问题

快速排序的基本步骤如下

（1） 选择基准元素（Pivot）： 从数组中选择一个元素作为基准元素（pivot）

通常有三种选择方法：

1. 选择第一个元素作为基准

2. 选择最后一个元素作为基准

3.选择中间位置的元素作为基准

（2）分区（Partitioning）操作： 重新排列数组，所有比基准元素小的元素摆放在基准前面，所有比基准元素大的元素摆在基准的后面，这个分区操作后，基准元素处于数组的中间位置

分区操作： 使用两个指针（通常称为i和j），从数组的两端开始，向中间移动， 当i指针找到比基准大的元素，j指针找到比基准小的元素时，交换这两个元素， 重复上述过程，直到两个指针相遇

#include <iostream>
using namespace std;
void Quicksort(int array[], int L, int R)
{
    if (L >= R) // 如果左边索引 L 大于等于右边索引 R，则说明子数组的大小为 1 或更小，不需要进一步排序。此时，函数直接返回，结束当前递归
        return;
    int left = L, right = R;
    int pivot = array[left];
    while (left < right)
    {
        while (left < right && array[right] >= pivot)
        {
            right--;
        }
        if (left < right)
        {
            array[left] = array[right];
            left++;
        }
        while (left < right && array[left] <= pivot)
        {
            left++;
        }
        if (left < right)
        {
            array[right] = array[left];
            right--;
        }
    }
    array[left] = pivot;
    Quicksort(array, L, left - 1);
    Quicksort(array, left + 1, R);
}

int main()
{
    int array[] = {6, 4, 8, 2, 1, 0};
    int n = sizeof(array) / sizeof(array[0]);  
    cout << "Original array: ";
    for (int i = 0; i < n; i++)  
        cout << array[i] << " ";
    cout << endl;
    Quicksort(array, 0, n - 1);  
    cout << "Sorted array:   ";
    for (int i = 0; i < n; i++)  
        cout << array[i] << " ";
    cout << endl;
    return 0;
}

参数说明：

array[]：待排序的整数数组

L：当前子数组的左边界索引 

R：当前子数组的右边界索引

函数逻辑：

递归终止条件：如果 L >= R，说明子数组的大小为 1 或更小，不需要排序，直接返回

初始化：将 left 和 right 分别初始化为 L 和 R，选择 array[left] 作为基准元素 pivot

分区操作：

从右向左扫描，找到第一个小于 pivot 的元素，将其放到 left 位置，并将 left 指针右移一位

从左向右扫描，找到第一个大于 pivot 的元素，将其放到 right 位置，并将 right 指针左移一位

重复上述两个步骤，直到 left 和 right 指针相遇

放置基准元素：将基准元素 pivot 放到 left 位置

递归排序：分别对基准元素左边和右边的子数组进行递归排序