【初阶数据结构题目】38. 快速排序-非递归版本

本文主要是介绍【初阶数据结构题目】38. 快速排序-非递归版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

非递归版本

非递归版本的快速排序需要借助数据结构：栈

思路：

假设我们初始要排序的数是：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;
}