// 使用队列实现快速排序非递归
#include <iostream>
#include <queue>
using namespace std;

// 快速排序中的一趟排序，返回基准值的索引
int partition(int arr[], int left, int right) {
    int pivot = arr[left]; // 选择最左边的元素作为基准
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

// 快速排序非递归算法
void quickSortNonRecursive(int arr[], int left, int right) {
    queue<int> q;
    q.push(left);
    q.push(right);
    while (!q.empty()) {
        left = q.front();
        q.pop();
        right = q.front();
        q.pop();
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            q.push(left);
            q.push(pivotIndex - 1);
            q.push(pivotIndex + 1);
            q.push(right);
        }
    }
}

// 主函数，用于测试快速排序非递归算法
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSortNonRecursive(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}