数据结构之 【排序】(非递归实现快速排序)

目录

1.引入

 2.非递归实现快排的思想

3.非递归实现快排图解

4.完整代码

1.引入

递归不可避免的话题就是防止栈溢出

所以程序员需要具备递归改非递归的能力 ，一般来说，抓住递归中变化的量是关键

void QuickSort(int* a, int left, int right){
	if (left >= right)
		return;

	if (right - left + 1 < 10){
		InsertSort(a + left, right - left + 1);
	}
	else{
		int keyi = PartSort1(a, left, right);
		//[left, keyi - 1] keyi [keyi + 1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

递归调用实现快速排序类似于二叉树的前序遍历(根、左子树、右子树)

仔细观察可知，栈帧中变化的是具体的区间边界

 2.非递归实现快排的思想

配合使用栈这种结构以模拟递归实现快排时的前序遍历

先将起始区间边界存入栈中，然后取出边界，进行快排的单趟排序得到分界位置的下标，以此为界将数组分割为左右两部分，然后先将右部分的区间边界存入栈中，再将左部分的区间边界存入栈中(区间大小大于1才将边界存入栈中)，再从栈中取出区间边界进行单趟排序，再分割数组并存入区间边界....直到栈为空为止

简单来说就是存边界、取边界排序、分数组存边界、取边界排序、分数组存边界.......

3.非递归实现快排图解

依据思想， 存边界、取边界排序、分数组存边界、取边界排序、分数组存边界.......

直到栈为空时停止，此时数组有序

4.完整代码

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//压栈
void STPush(ST* ps, STDataType val);
//出栈
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//访问栈顶
STDataType STTop(ST* ps);

void QuickSortNonR(int* a, int left, int right){
	//区间不存在就返回
    if (left >= right)
		return;
    //小规模数组直接优化
	if (right - left + 1 < 10){
		InsertSort(a + left, right - left + 1);
		return;
	}
    //C语言实现的栈
	ST st;
	STInit(&st);
    //先压右，再压左，顺次取出就是区间
	STPush(&st, right);
	STPush(&st, left);
	while (!STEmpty(&st)){
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
        //小规模数组直接优化
		if (end - begin + 1 < 10){
			InsertSort(a + begin, end - begin + 1);
			continue;
		}

		int keyi = PartSort3(a, begin, end);
		//[begin, keyi - 1] keyi [keyi + 1, end]
		if (begin < keyi - 1){
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
		if (keyi + 1 < end){
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
	}
	STDestroy(&st);
}

注意边界的存入方式 、小规模数组可以进行优化