排序算法：快速排序（非递归）-Toy模板网

这篇具有很好参考价值的文章主要介绍了排序算法：快速排序（非递归）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

!

先赞后看，养成习惯！！！^ _ ^<3 ❤️ ❤️ ❤️
码字不易，大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦！
所属专栏:排序算法

思路如下：

一、先建立一个栈

为什么要建立栈呢？
建立栈是为了让每次排序的区间进去，然后后面便于取出

排序算法：快速排序（非递归）,排序算法,排序算法,算法

二、代码编写

这里用了之前的快速排序的一个格式（前后指针法）
注意事项：
1.每次判断key-1和key+1是否符合要求（keyi-1>left ，keyi+1<right）这样才能入栈
2.前后指针法排序时必须记住当cur走到right的时候，prev所在的位置一定小于或者等于key，此时出了循环一定要和left位置的值交换，这样可以使得key的位置已经排好了

void Swap(int* p1, int* p2)
{
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

int QuickSort(int left,int right,int* a)
{
	int prev = left;
	int cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] <= key && ++prev != cur)
			Swap(&a[cur],&a[prev]);
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}


void TestQuickSort(int begin,int end,int* a)
{
	ST stack;
	StackInit(&stack);
	StackPush(&stack, end);
	StackPush(&stack, begin);
	while (!StackEmpty(&stack))
	{
		int left = StackTop(&stack);
		StackPop(&stack);
		int right = StackTop(&stack);
		StackPop(&stack);

		int keyi = QuickSort(left, right, a);

		if (keyi + 1 < right)
		{
			StackPush(&stack, right);
			StackPush(&stack, keyi + 1);
		}
		if (keyi - 1 > left)
		{
			StackPush(&stack, keyi - 1);
			StackPush(&stack, left);
		}
	}


	StackDestroy(&stack);


}

int main()
{
	int a[10] = { 3,5,6,7,2,1,8,10,9,4 };
	TestQuickSort(0,9,a);
	for (int i = 0; i < 10; i++)
		printf("%d ",a[i]);
	return 0;
}