我有一个递归快速排序的C实现，我想把它转换成一个迭代使用堆栈。
这是我在C中的实现：
int random_partition(int* arr, int start, int end) {
srand(time(NULL));
int random_pivot = rand() % (start - end) + start;
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;
}
void quick_sort(int* arr, int start, int end) {
if (start < end) {
int pivot_index = random_partition(arr, start, end);
quick_sort(arr, start, pivot_index - 1);
quick_sort(arr, pivot_index + 1, end);
}
}这是我做的事情，但是当弹出时，我什么也不做，因为在递归中，这就是我们所做的。
void quick_sort_iter(int* arr, int start, int end) {
stack* s = create_stack(n);
int pivot_index = random_partition(arr, start, end);
int p = pivot_index;
while (start < pivot_index) {
pivot_index = random_partition(arr, start, end);
push(s, start);
push(s, pivot_index--);
}
pivot_index = p;
while (pivot_index < end) {
push(s, pivot_index++);
push(s, end);
pivot_index = random_partition(arr, start, end);
}
while(!is_empty(s)) {
int e = pop(s);
int s = pop(s);
// do nothing, because in recursion the return doesn't do anything
}
return arr;
}我首先要问的是，这是不是应该走的路，或者如何处理？
1条答案
按热度按时间lvmkulzt1#
你的两个循环只会创建从最左边开始（在
start）或在最右边结束（在end）的分区，但是正确的算法也会创建不在数组的任何一个极端边界的分区。要实现这一点，首先将完整的数组范围推到堆栈上，然后在一个循环中，从堆栈中弹出一个范围，如果它至少有两个元素，则对其进行分区，并将生成的两个分区范围推回到堆栈上。继续这样做，直到堆栈中没有任何内容：
一些评论：
start和end在循环中进行本地管理。因此，调整main的调用，使其只传递数组指针和数组大小。void，不应该返回数组。数组是就地排序的，就像递归实现一样。n作为堆栈大小，但不清楚n表示什么值。在这里，我使用数组大小的两倍（每次我们推送一对索引时）作为堆栈的大小，这足以覆盖最坏的情况。因为你有一个随机的pivot选择，所以堆栈的预期空间使用是O（log𝑛）。正如注解中所指出的，你可以𝑛通过首先将较大的分区放在堆栈上来使其成为最大值（2log2个条目）。