用C++写一跟非递归快速排序

以下是用C语言实现的非递归快速排序代码：

#include <stdio.h>
#define MAX_SIZE 100000

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quick_sort(int arr[], int left, int right) {
    int stack[MAX_SIZE];
    int top = -1;
    
    stack[++top] = left;
    stack[++top] = right;

    while (top >= 0) {
        right = stack[top--];
        left = stack[top--];

        int pivot = arr[right];
        int i = left - 1;

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

        swap(&arr[i+1], &arr[right]);

        int mid = i + 1;

        if (mid - 1 > left) {
            stack[++top] = left;
            stack[++top] = mid - 1;
        }

        if (mid + 1 < right) {
            stack[++top] = mid + 1;
            stack[++top] = right;
        }
    }
}

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

    printf("Before sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quick_sort(arr, 0, n-1);

    printf("After sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

该算法使用一个栈来存储需要进行排序的子序列的起始和结束位置。在每次循环中，弹出栈顶的两个位置，进行一次快速排序，如果需要再将分割点的左右两边分别入栈。直到栈为空，排序完成。