快速排序的非递归版不用栈实现C语言实现

快速排序的非递归版可以使用数组模拟栈的操作，也可以使用指针实现。以下是使用指针实现的C语言代码：

#include <stdio.h>

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

void quickSort(int arr[], int left, int right) {
    int stack[right - left + 1];
    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 pivotIndex = i + 1;

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

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

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {5, 9, 1, 3, 10, 4, 8, 6, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, size - 1);
    printf("Sorted array: ");
    printArray(arr, size);
    return 0;
}

这个实现中，我们使用一个指针数组 `stack` 来模拟栈的操作，`top` 指针表示当前栈顶元素的位置。我们首先将左右边界压入栈中，然后在 while 循环中进行以下操作：

- 弹出栈顶的右边界和左边界
- 选择最后一个元素作为 pivot，进行快速排序的划分操作
- 将 pivot 移动到正确的位置上
- 根据 pivot 的位置将左右两个子数组的边界压入栈中

这样我们可以使用 O(1) 的空间复杂度来实现快速排序的非递归版。