快速排序(非递归版本)

引言

在排序算法的世界里，快速排序以其高效的性能脱颖而出。它采用分治法的思想，通过选择基准元素将数组分为两部分，递归地对左右两部分进行排序。然而，递归实现的快速排序在处理大规模数据时可能会导致栈溢出的问题。为了解决这个问题，我们可以使用非递归的方式来实现快速排序。

快速排序原理回顾

快速排序的基本思想是选择一个基准元素，将数组分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于等于基准元素。然后递归地对左右两部分进行排序，最终得到一个有序的数组。

递归与非递归的区别

递归实现的快速排序使用系统栈来保存每一层递归调用的状态。当数组规模较大时，递归深度会变得很深，可能会导致系统栈溢出。而非递归实现则使用自定义的栈来模拟递归调用的过程，避免了系统栈溢出的问题。

非递归快速排序的实现思路

非递归快速排序的核心是使用自定义的栈来模拟递归调用的过程。具体步骤如下：

选择一个基准元素并将数组分为两部分，返回基准元素的最终位置。
将待排序的区间（左右边界）压入栈中。
每次从栈中取出一个区间进行分区操作，然后将新的子区间压入栈中。
重复步骤 3，直到栈为空。

大概思路画法：

一、快速排序非递归实现

// 前后指针版本
int _QuickSort(int* arr, int left, int right) {int keyi = left;int prev = left;int cur = left + 1;while (cur <= right) {if (arr[cur] < arr[keyi] && ++prev != cur) {swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[keyi], &arr[prev]);keyi = prev;return keyi;
}//快速排序非递归
void QuickSort(int* arr, int left, int right) {Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)) {int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = _QuickSort(arr, begin, end);if (keyi + 1 < end) {StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

1. 分区函数 `_QuickSort`

功能：选择 arr[left] 作为基准元素，通过前后指针法将数组分为两部分，返回基准元素的最终位置。
核心逻辑：
- prev 指针标记小于基准的元素边界，cur 遍历数组；
- 当 arr[cur] < arr[keyi] 时，prev 后移并交换 arr[prev] 与 arr[cur]；
- 最后将基准元素与 prev 指向的元素交换，确保基准归位。

2. 非递归主函数 `QuickSort`

核心思路：使用栈模拟递归调用，避免系统栈溢出风险。
代码流程：
1. 初始化栈：创建栈 st，并将初始区间 [left, right] 压入栈中。
2. 循环处理：当栈不为空时，取出栈顶的左右边界 begin 和 end；
3. 分区操作：调用 _QuickSort 对区间 [begin, end] 分区，获取基准位置 keyi；
4. 子区间入栈：若基准两侧子区间长度大于 1，则将其边界压入栈中，等待后续处理；
5. 清理资源：排序完成后，销毁栈对象。

3. 性能与应用

时间复杂度：平均 \(O(n \log n)\)，最坏 \(O(n^2)\)（如数组有序时）。
空间复杂度：依赖栈空间，平均 \(O(\log n)\)，最坏 \(O(n)\)。
适用场景：适合处理大规模数据，非递归实现尤其适合对栈深度有限制的环境。

代码sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack {STDataType* _a;int _top;int _capacity;
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈---栈顶
void StackPush(Stack* ps, STDataType data);
// 出栈——栈顶
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 检测栈是否为空，如果为空返回true结果，如果不为空返回flse 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
//快速排序
void QuickSort(int* arr, int left, int right);

代码sort.c

#include"sort.h"// 初始化栈 
void StackInit(Stack* ps) {ps->_a = NULL;ps->_capacity = ps->_top = 0;
}
// 入栈---栈顶
void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps->_capacity == ps->_top) {int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("Fail realloc");exit(1);}ps->_a = tmp;ps->_capacity = newCapacity;}ps->_a[ps->_top++] = data;
}
// 检测栈是否为空，如果为空返回true结果，如果不为空返回flse 
bool StackEmpty(Stack* ps) {return ps->_top == 0;
}
// 出栈——栈顶
void StackPop(Stack* ps) {assert(!StackEmpty(ps));ps->_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps) {assert(!StackEmpty(ps));return ps->_a[ps->_top - 1];
}
// 销毁栈 
void StackDestroy(Stack* ps) {if (ps->_a)free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}void swap(int* x, int* y) {int tmp = *x;*x = *y;*y = tmp;
}
// 前后指针版本
int _QuickSort(int* arr, int left, int right) {int keyi = left;int prev = left;int cur = left + 1;while (cur <= right) {if (arr[cur] < arr[keyi] && ++prev != cur) {swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[keyi], &arr[prev]);keyi = prev;return keyi;
}
//快速排序
void QuickSort(int* arr, int left, int right) {Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)) {int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = _QuickSort(arr, begin, end);// [begin,keyi-1] keyi [keyi+1,emd]if (keyi + 1 < end) {StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);}

代码test.c

#include"sort.h"
void test01() {int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int size = sizeof(arr) / sizeof(arr[0]);QuickSort(arr, 0, size - 1);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}
}int main() {test01();return 0;
}