C++ 快速排序 非递归版本 代码

快速排序是一种常用的排序算法，其非递归版本的代码如下：

void quickSort(int arr[], int left, int right) {
    int stack[right - left + 1];
    int top = -1;
    stack[++top] = left;
    stack[++top] = right;
    while (top >= ) {
        right = stack[top--];
        left = stack[top--];
        int pivot = partition(arr, left, right);
        if (pivot - 1 > left) {
            stack[++top] = left;
            stack[++top] = pivot - 1;
        }
        if (pivot + 1 < right) {
            stack[++top] = pivot + 1;
            stack[++top] = right;
        }
    }
}

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

该算法使用了一个栈来模拟递归调用，从而实现了非递归版本的快速排序。具体来说，每次将待排序区间的左右端点入栈，然后循环执行以下操作：

1. 出栈左右端点，对该区间进行分区操作，得到枢轴元素的位置。
2. 如果枢轴元素左边的区间长度大于1，则将左右端点入栈。
3. 如果枢轴元素右边的区间长度大于1，则将左右端点入栈。

当栈为空时，排序完成。