利用快排的partition算法进行排序并输出每一趟结果C++

快速排序是一种高效的排序算法，其基本思想是分治法。其中partition函数是关键步骤，它将数组分为两部分：一部分的所有元素都小于另一部分的元素，然后对这两部分分别递归地应用快速排序。

以下是使用C++实现快速排序，并在每轮分区后输出数组状态的一个简化版本：

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 小于基准的元素的索引

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) { // 如果当前元素小于基准
            i++; // 更新索引
            swap(arr[i], arr[j]); // 交换当前位置和i位置的元素
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准放到正确的位置
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 对基准左边的子数组和右边的子数组分别递归调用quickSort
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "After each pass of partitioning: \n";
    for (int i = 0; i <= n - 1; i++) {
        printArray(arr, n);
        cout << "---------------------------\n";
    }

    return 0;
}

在这个示例中，`quickSort` 函数首先调用 `partition` 来划分数组，然后分别对划分后的两个子数组递归调用自身。每次分区后，都会调用 `printArray` 显示数组的新状态。