排序算法——快速排序的非递归写法

快速排序的非递归

我们写快速排序的时候，通常用的递归的方法实现快速排序，那么有没有非递归的方法实现快速排序呢？肯定是有的。思想还是一样的，不过非递归是看似是非递归其实还是递归。

思路解释

快速排序的非递归使用的是栈这个数据结构。我们知道栈是后入先出和先入后出的，所以我们可以通过栈的方式模拟递归，然后实现快速排序的非递归。

如图所示，创建一个栈。然后首先先将数组的起始和末尾的下标存进栈中，然后让left=begin，right=end，并pop出去。然后进行一次快排找到keyi。此时如果keyi两边的区间（绿色的）存在，就把keyi也存进栈。然后进行一次快排，当区间为空或者区间值有序，就把值从栈中pop出来，如果不是，就继续push进去，直到栈为空。最后别忘了把栈给销毁。

代码

int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{if (a[midi] > a[end])return midi;else if (a[begin] < a[end])return begin;elsereturn end;}
}
int PSort(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[key] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}Swap(&a[key], &a[prev]);key = prev;return key;
}
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PSort(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}

下面是栈的头文件和.c文件

#include <stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct Stack
{int* a;int top;		// 标识栈顶位置的int capacity;
}ST;
void STInit(ST* pst);//初始化栈
void STDestroy(ST* pst);//栈的销毁
void STPush(ST* pst, int x);//栈顶插入
void STPop(ST* pst);//栈顶删除
int STTop(ST* pst);//获取栈顶元素
bool STEmpty(ST* pst);//检查栈是否为空
int STSize(ST* pst);//获取栈中元素的个数

#include "stack.h"
void STInit(ST* pst)
{/*ST* tmp = (ST*)malloc(sizeof(ST));if (tmp == NULL){perror("malloc");return;}*/pst->a = NULL;pst->top = -1;pst->capacity = 0;
}
void STPush(ST* pst, int x)
{assert(pst);if (pst->top == pst->capacity - 1){int newcapacite = pst->capacity == 0 ? 4 : pst->capacity * 2;int* tmp = (int*)realloc(pst->a, newcapacite * sizeof(int));if (tmp == NULL){perror("realloc");return;}pst->a = tmp;pst->capacity = newcapacite;}pst->a[pst->top + 1] = x;pst->top++;
}
void STPop(ST* pst)
{assert(pst);pst->top--;
}
int STTop(ST* pst)
{assert(pst);if (pst->top == -1){printf("此栈为空");return 1;}return pst->a[pst->top];
}
bool STEmpty(ST* pst)
{assert(pst);return pst->top == -1;
}
int STSize(ST* pst)
{assert(pst);return pst->top++;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = -1;}