非递归版本
非递归版本的快速排序需要借助数据结构：栈
思路：
假设我们初始要排序的数是：
5 3 9 6 2 4经过一轮快速排序后，找到的基准值是
6，也就是keyi=3通过一轮快速排序后，接下来要排序的数是
2 3 4 5 6 9
如果
left=0，right=5，keyi=3左区间：
[left,keyi-1] [0,2]右区间：
[keyi+1,right] [4,5]先把右区间的
right：5入栈，然后把右区间的left：4入栈然后把左区间的
right：2入栈，然后把左区间的left：0入栈
此时栈里面是：
0 2 4 5
然后出栈两次，取到
left=0，right=2我们对下标为
0-2的数找基准值找到基准值
keyi=0
此时
left=0，right=2，keyi=1左区间：
[left,keyi-1] [0,-1]非有效区间，不入栈右区间：
[keyi+1,right] [1,2]先把右区间的
right：2入栈，然后把右区间的left：1入栈
此时栈里面是：
1 2 4 5
然后出栈两次，取到
left=1，right=2我们对下标为
1-2的数找基准值找到基准值
keyi=1
此时
left=1，right=2，keyi=1左区间：
[left,keyi-1] [1,0]非有效区间，不入栈右区间：
[keyi+1,right] [2,2]非有效区间，不入栈
此时栈里面是：
4 5
然后出栈两次，取到
left=4，right=5我们对下标为
4-5的数找基准值找到基准值
keyi=4
此时
left=4，right=5，keyi=4左区间：
[left,keyi-1] [4,3]非有效区间，不入栈右区间：
[keyi+1,right] [5,5]非有效区间，不入栈
此时排完序了，是
2 3 4 5 6 9我们销毁函数栈。
代码实现：
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#include <assert.h>//打印
void PrintArr(int* arr, int n);
//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right);
Sort.c
#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity; //栈的空间大小int top; //栈顶
}ST;//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x)
{assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//栈顶出数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//栈的销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;//创建栈STInit(&st);//栈的初始化StackPush(&st, right);//栈顶入数据StackPush(&st, left);//栈顶入数据while (!StackEmpty(&st))//栈不为空就进入循环{//取栈顶元素---取两次int begin = StackTop(&st);StackPop(&st);//栈顶出数据int end = StackTop(&st);StackPop(&st);//栈顶出数据//[begin,end]---找基准值//双指针法int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur)//这里<和<=一样{Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);//上面循环结束说明cur越界了keyi = prev;//根据基准值keyi划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]if (keyi + 1 < end){StackPush(&st, end);//右区间入栈StackPush(&st, keyi + 1);//左区间入栈}if (keyi - 1 > begin){StackPush(&st, keyi - 1);//右区间入栈StackPush(&st, begin);//左区间入栈}}STDestroy(&st);//销毁栈
}
test.c
#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSortNonR(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}
