将C语言递归快速排序转换为栈实现的迭代版本的方法咨询

你的当前思路完全不可行，核心问题是误解了递归转迭代时栈的作用：递归中每次调用quick_sort是处理一个待排序区间，栈应该存储这些待处理的区间，而不是提前分区后压入无效索引；而且你弹出栈后不对区间做任何处理，完全违背了迭代模拟递归的逻辑。另外你的代码还有几个明显错误：

• random_partition里的rand() % (start - end) + start计算错误，应该是rand() % (end - start + 1) + start，否则当start < end时，start - end是负数，取模会导致未定义行为。
• 弹出栈时用了int s = pop(s);，变量名和栈变量s重名，会导致编译错误。
• 提前执行分区的逻辑混乱，没有按照递归流程处理子区间。

正确的迭代版快速排序实现思路 #

递归版快排的逻辑是：处理区间[start, end] → 分区得到pivot → 递归处理左区间[start, pivot-1] → 递归处理右区间[pivot+1, end]。用栈模拟时，栈的作用就是存储待处理的区间，流程如下：

1. 初始化栈，将初始区间[start, end]压入栈（注意栈是后进先出，压入顺序要对应弹出顺序）。
2. 循环直到栈为空：
   • 弹出一个待处理的区间（先弹end，再弹start，因为压入时先压start再压end的话，弹出顺序相反）。
   • 如果start >= end，跳过（对应递归的终止条件）。
   • 对当前区间执行分区，得到pivot_index。
   • 将右区间[pivot_index+1, end]压入栈，再将左区间[start, pivot_index-1]压入栈（这样弹出时会先处理左区间，和递归顺序一致）。

另外注意：srand(time(NULL))不要放在random_partition里，否则每次分区都会重置随机种子，导致随机pivot重复，应该在调用快排前执行一次。

修正后的完整代码 #

首先修正random_partition及补充栈实现：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 修正后的随机分区函数
int random_partition(int* arr, int start, int end) {
    // 生成[start, end]范围内的随机索引
    int random_pivot = start + rand() % (end - start + 1);
    swap(&arr[random_pivot], &arr[end]);
    int pivot = arr[end], pivot_index = start;
    for (int i = start; i < end; i++) {
        if (arr[i] <= pivot) {
            swap(&arr[pivot_index], &arr[i]);
            pivot_index++;
        }
    }
    swap(&arr[pivot_index], &arr[end]);
    return pivot_index;
}

// 栈的结构定义
typedef struct Stack {
    int* data;
    int top;
    int capacity;
} stack;

stack* create_stack(int capacity) {
    stack* s = (stack*)malloc(sizeof(stack));
    s->capacity = capacity;
    s->top = -1;
    s->data = (int*)malloc(sizeof(int) * capacity);
    return s;
}

void push(stack* s, int val) {
    if (s->top == s->capacity - 1) {
        return;
    }
    s->data[++s->top] = val;
}

int pop(stack* s) {
    if (s->top == -1) {
        return -1;
    }
    return s->data[s->top--];
}

int is_empty(stack* s) {
    return s->top == -1;
}

然后是迭代版快排：

// 迭代版快排
void quick_sort_iter(int* arr, int start, int end) {
    // 创建栈，容量足够存储区间即可
    stack* s = create_stack(end - start + 1);
    
    // 压入初始区间：先压start，再压end
    push(s, start);
    push(s, end);
    
    while (!is_empty(s)) {
        // 弹出区间：先弹end，再弹start
        int curr_end = pop(s);
        int curr_start = pop(s);
        
        // 终止条件：区间无效
        if (curr_start >= curr_end) {
            continue;
        }
        
        // 分区得到pivot索引
        int pivot_index = random_partition(arr, curr_start, curr_end);
        
        // 压入右区间：[pivot_index+1, curr_end]
        push(s, pivot_index + 1);
        push(s, curr_end);
        
        // 压入左区间：[curr_start, pivot_index-1]
        push(s, curr_start);
        push(s, pivot_index - 1);
    }
    
    // 释放栈内存
    free(s->data);
    free(s);
}

测试示例 #

int main() {
    // 只初始化一次随机种子
    srand(time(NULL));
    
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    quick_sort_iter(arr, 0, n-1);
    
    printf("排序后数组：");
    for (int i=0; i<n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

内容的提问来源于stack exchange，提问作者Kim