c中双链表迭代快速排序

Question

我这里有一个函数来快速排序一个使用递归方法的双重链表。我想知道如何把这个函数从递归变成迭代快速排序。我一直在努力，但我就是搞不懂它是怎么做的。

编辑:我已经修改了代码，我无法得到列表排序。我只是遵循了如何使用数组实现快速排序的算法。但是没有错误。

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int val;
struct Node *next;
struct Node *prev;
};
struct Stack
{
struct Node* top;
};
typedef struct Stack *stackPtr;
struct Node *CreateNode(int data)
{
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->next = newNode->prev = NULL;
newNode->val = data;

return newNode;
}
stackPtr CreateStack()
{
stackPtr stack = (stackPtr)malloc(sizeof(struct Stack));
stack->top = NULL;
}
void Push(stackPtr stack, int data)
{
struct Node *newNode = CreateNode(data);
newNode->next = stack->top;
stack->top = newNode;   
}
void Pop(stackPtr stack)
{
struct Node *temp;
temp = stack->top;
stack->top = stack->top->next;
free(temp);
}
struct Node *partition(struct Node *left, struct Node *right)
{
struct Node *pivot = right;
struct Node *i = left->prev;
struct Node *ptr;
for (ptr = left; ptr != right; ptr = ptr->next)
{
if (ptr->val <= pivot->val)
{
i = (i == NULL ? left : i->next);
int temp = i->val;
i->val = ptr->val;
ptr->val = temp;
}
}
i = (i == NULL ? left : i->next);
int temp = i->val;
i->val = pivot->val;
pivot->val = temp;
return i;
}
void QuickSort(struct Node *left, struct Node *right)
{    
stackPtr auxStack = CreateStack();
Push(auxStack, left->val);
Push(auxStack, right->val);

while(auxStack->top != NULL)
{
Pop(auxStack);
}

struct Node *pivot = partition(left, right);

if((pivot->val - 1) > left->val)
{
Push(auxStack, left->val);
Push(auxStack, (pivot->val - 1));
}

if((pivot->val + 1) < right->val)
{
Push(auxStack, (pivot->val + 1));
Push(auxStack, right->val);
}
}
int main()
{
struct Node *head = malloc(sizeof(struct Node));
head->val = 2;
head->prev = NULL;
struct Node *l1 = malloc(sizeof(struct Node));
l1->val = 8;
l1->prev = head;
head->next = l1;
struct Node *l2 = malloc(sizeof(struct Node));
l2->val = 3;
l2->prev = l1;
l1->next = l2;
struct Node *l3 = malloc(sizeof(struct Node));
l3->val = 5;
l3->prev = l2;
l2->next = l3;
struct Node *l4 = malloc(sizeof(struct Node));
l4->val = 10;
l4->prev = l3;
l3->next = l4;
l4->next = NULL;
// 2<=>8<=>3<=>5<=>10=>NULL
QuickSort(head, l4);
while (head != NULL)
{
printf("%d ", head->val);
head = head->next;
}
return 0;
}

Answer 1

假设您有一个工作的递归快速排序函数:

void quicksort_rec(int *a, const int *end)
{
if (a + 1 < end) {
int *pivot = partition(a, end);
quicksort_rec(a, pivot);
quicksort_rec(pivot + 1, end);
}
}

(这是对数组的快速排序，它以指向数组开始和(不包括)结束的指针的形式接受范围。)不考虑配分函数的细节)

当你递归地调用quicksort_rec时，被调用函数的局部变量存储在调用堆栈中:"parent"随着递归深度的增加，递归仍然可用。

如果你想把它变成一个迭代函数，你必须手动维护一个堆栈。(John Bollinger在评论中比我描述得更详细、更好)

所以不调用quicksort(a, b)，必须将a和b压入堆栈以"保存它们以备以后使用"。栈上最后被压入的东西是最先被弹出的东西，所以右边的数组将被排序。

给定存储指向int的指针的堆栈实现，可以将上面的递归函数转换为迭代函数:

void quicksort_iter(int *a, int *end)
{
Stack stack = {0};

push(&stack, a);
push(&stack, end);
while (isempty(&stack)) {
end = pop(&stack);
a = pop(&stack);

if (a + 1 < end) {
int *pivot = partition(a, end);

push(&stack, a);
push(&stack, pivot);

push(&stack, pivot + 1);
push(&stack, end);
}
}
}

这段代码总是同时推入或弹出两个项目。注意，开始和结束指针的弹出顺序必须与它们被推送的顺序相反。您也可以创建一个包含两个指针的结构体，并始终推送一个这样的结构体，这样可能更简洁。如果子数组的元素少于两个，你也可以通过不将子数组压入堆栈来优化这一点。

确切的实现留给读者，yadda, yadda，…:)但是这里是上面代码的完整实现，可以让您开始。