快速排序挖坑法c++

快速排序的挖坑法是一种常用的快速排序算法实现方式。这种方式通过将待排序序列分成两部分，一部分小于基准值，一部分大于基准值，然后对这两部分递归地进行排序，最终得到有序序列。具体步骤如下：

1. 选择一个基准值，通常是待排序序列的第一个元素。
2. 从序列的末尾开始，设两个指针i和j，分别指向序列的起始位置和末尾位置。
3. 先从右往左扫描，找到第一个小于基准值的元素a[j]，将其放到a[i]的位置上，并将i加1。
4. 再从左往右扫描，找到第一个大于基准值的元素a[i]，将其放到a[j]的位置上，并将j减1。
5. 重复步骤3和4，直到i和j相遇。
6. 将基准值放到i和j相遇的位置上。
7. 递归地对基准值左边的序列和右边的序列进行排序，直到每个子序列只有一个元素。

以下是给出的示例代码实现了快速排序的挖坑法：

#include <iostream>
using namespace std;

void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];  // 选择第一个元素作为基准值
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];  // 将小于基准值的元素移到左边
            i++;
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];  // 将大于基准值的元素移到右边
            j--;
        }
    }
    arr[i] = pivot;  // 将基准值放到i和j相遇的位置上
    quickSort(arr, left, i - 1);  // 对基准值左边的序列递归排序
    quickSort(arr, i + 1, right);  // 对基准值右边的序列递归排序
}

int main() {
    int arr[] = {9, 5, 2, 7, 3, 6, 8, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}