非递归实现快速排序c++

下面是一个非递归实现快速排序的C代码示例：

#include <stdio.h>

// 用于交换数组中两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 划分函数，将数组划分为两部分，并返回划分点的下标
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选取最后一个元素作为基准
    int i = (low - 1);  // i为小于等于基准的元素的最右位置

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于等于基准，则将其放到左侧
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);  // 将基准放到正确的位置
    return (i + 1);  // 返回基准的位置
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    // 创建一个栈用于存储需要排序的子数组的起始和结束位置
    int stack[high - low + 1];
    int top = -1;

    // 初始化栈
    stack[++top] = low;
    stack[++top] = high;

    // 循环直到栈为空
    while (top >= 0) {
        // 从栈中取出需要排序的子数组的起始和结束位置
        high = stack[top--];
        low = stack[top--];

        // 将数组划分为两部分，并获取基准的位置
        int pivot = partition(arr, low, high);

        // 如果基准左侧有更多元素，则将左侧的子数组入栈
        if (pivot - 1 > low) {
            stack[++top] = low;
            stack[++top] = pivot - 1;
        }

        // 如果基准右侧有更多元素，则将右侧的子数组入栈
        if (pivot + 1 < high) {
            stack[++top] = pivot + 1;
            stack[++top] = high;
        }
    }
}

// 测试快速排序
int main() {
    int arr[] = {9, -2, 5, 3, 10, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    quickSort(arr, 0, n - 1);

    printf("\n排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

这段代码使用了一个栈来模拟递归调用的过程，通过不断将需要排序的子数组的起始和结束位置入栈，并在循环中出栈并划分数组，直到栈为空，完成排序。