快速排序(非递归版本)

引言

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

快速排序原理回顾

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

递归与非递归的区别

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

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

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

1. 选择一个基准元素并将数组分为两部分，返回基准元素的最终位置。
2. 将待排序的区间（左右边界）压入栈中。
3. 每次从栈中取出一个区间进行分区操作，然后将新的子区间压入栈中。
4. 重复步骤 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;
}