【数据结构】快速排序（不用递归）

大家好，我是苏貝，本篇博客带大家了解快速排序的非递归方法，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

上一篇博客我们讲了如何实现使用递归的快速排序，今天我们再来了解一下如何不用递归实现快速排序
快速排序（用递归）

思路:

在这里插入图片描述

我们先插入数组的末尾元素的下标，再插入首元素的下标。当栈为空时，表示数字已经排好了序，此时循环停止。当左右子树为一个元素或者为空时，不用将下标插入栈中，为一个元素的条件是：left==keyi - 1或者keyi + 1 ==right，为空的条件是left > keyi - 1或者keyi + 1 > right

void QuickSortNonR(int* a, int left, int right)
{
	ST p;
	STInit(&p);
	STPush(&p, right);
	STPush(&p, left);

	while (!STEmpty(&p))
	{
		left = STTop(&p);
		STPop(&p);
		right = STTop(&p);
		STPop(&p);

		int keyi = PartSort1(a, left, right);
		if (left < keyi - 1)
		{
			STPush(&p, keyi - 1);
			STPush(&p, left);
		}
		if (keyi + 1 < right)
		{
			STPush(&p, right);
			STPush(&p, keyi + 1);
		}
	}
	
	STDestroy(&p);
}

完整代码：

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] > a[midi])
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[end] > a[begin])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[end] < a[begin])
			return begin;
		else if (a[midi] < a[end])
			return midi;
		else
			return end;
	}
}


//hoare版本
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[begin], &a[midi]);

	int key = begin;
	int left = begin;
	int right = end;

	while (left < right)
	{
		//right先走，left后走
		while (left < right && a[right] >= a[key])
			right--;
		while (left < right && a[left] <= a[key])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);

	return left;
}


void QuickSortNonR(int* a, int left, int right)
{
	ST p;
	STInit(&p);
	STPush(&p, right);
	STPush(&p, left);

	while (!STEmpty(&p))
	{
		left = STTop(&p);
		STPop(&p);
		right = STTop(&p);
		STPop(&p);

		int keyi = PartSort1(a, left, right);
		if (left < keyi - 1)
		{
			STPush(&p, keyi - 1);
			STPush(&p, left);
		}
		if (keyi + 1 < right)
		{
			STPush(&p, right);
			STPush(&p, keyi + 1);
		}
	}


	STDestroy(&p);
}