【数据结构与算法】快速排序（下）性能分析及非递归实现

目录

一、性能分析

🍃时间复杂度：O(n log n)

🍃空间复杂度：O(log n)

🍃稳定性：不稳定

二、快速排序非递归实现

三、应用场景

​

一、性能分析

🍃时间复杂度：O(n log n)

1. 最好情况（O(n log n)）：
   当每次分区操作都能将数组分为两个大致相等的部分时，快速排序的性能最好。这种情况下，算法的时间复杂度为O(n log n)，其中n是数组的长度。这是因为每次分区后，问题规模减半，形成一棵深度为log n的平衡二叉树。

2. 最坏情况（O(n^2)）：
   当数组已经有序或几乎有序，且分区点总是选择到数组的最小值或最大值时，快速排序的性能会退化到O(n^2)。这是因为每次分区操作都会将一个元素（分区点）放到其最终位置，而另一个子数组保持不变，导致算法需要进行n-1次分区操作。

3. 平均情况（O(n log n)）：
   对于随机排列的数组，快速排序的平均时间复杂度也是O(n log n)。虽然存在最坏情况的风险，但通过随机选择分区点或使用三数取中等策略，可以大大降低遇到最坏情况的可能性。

🍃空间复杂度：O(log n)

• 递归栈空间（O(log n) 到 O(n)）：
  快速排序是递归的，因此需要使用系统栈来保存递归调用的状态。在最好情况下，递归深度为log n（平衡二叉树），但在最坏情况下，递归深度为n（链表结构）。不过，经过上述优化之后，最坏情况一般不会出现。

🍃稳定性：不稳定

• 快速排序不是一种稳定的排序算法。在排序过程中，相等元素的相对顺序可能会发生变化。如果需要稳定性，可以考虑使用归并排序等其他排序算法。

二、快速排序非递归实现

基本思路

通过迭代的方式实现快速排序，但实现过程中结合了递归快速排序的思想，并使用了一个栈（Stack）来模拟递归调用的栈行为。这种做法的主要目的是避免直接使用递归，从而在某些栈空间有限的环境下减少栈溢出的风险。

 迭代实现的基本思路

由于递归实现中，每次递归调用都会将数组的一个子区间（left, right）作为新的排序区间，因此迭代实现中需要使用一个栈来模拟这一过程。具体步骤如下：

• 初始化栈：使用一个栈来存储待排序的区间，初始时将整个数组区间（left, right）压入栈中。
• 循环处理栈：只要栈不为空，就不断从栈中取出区间（left, right），对这个区间进行快速排序处理（即选择基准值，进行分区），然后可能得到两个新的子区间（如果子区间长度大于1）。
• 子区间入栈：将得到的两个子区间（如果有的话）重新压入栈中，以便后续继续处理。
• 重复处理：重复上述过程，直到栈为空，此时所有区间都已处理完成，整个数组排序也就完成了。

代码实现中的关键点

• Quicksort 函数：这个函数实际上执行的是快速排序的分区操作，并返回基准值的最终位置。它负责将数组分为两部分，并返回这两部分的分界线（即基准值的最终位置）。
• QuickSortNonR 函数：这个函数是迭代快速排序的主函数，它使用栈来模拟递归过程。它首先初始化栈，并将整个数组的区间压入栈中，然后不断从栈中取出区间进行处理，并将新的子区间压回栈中，直到栈为空。
• 栈操作：代码中使用了自定义的栈结构（Stack），包括初始化（StackInit）、入栈（StackPush）、出栈（StackPop）、判断栈空（StackEmpty）、栈顶元素（StackTop）和销毁栈（StackDestroy）等操作。

C语言实现代码

CV了之前已经实现好的栈的代码

参考文章

【数据结构与算法】使用数组实现栈：原理、步骤与应用-云社区-华为云 (huaweicloud.com)

void Swap(int* a, int* b)//交换函数
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int  Quicksort(int* a, int left, int right)//快排hoare版子函数
{
	int midi = GetMid(a, left, right);//三个数取中间值的下标
	Swap(&a[left], &a[midi]);
	int keyi = left;
	int begin = left, end = right;

	while (begin < end)//begin与end未相遇时，继续循环
	{
		while (begin < end && a[end] >= a[keyi])//end先移动，找到小于keyi位置的值停止
			end--;
		while (begin < end && a[begin] <= a[keyi])//begin再移动，找到大于keyi位置的值停止
			begin++;
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], &a[begin]);//出循环后，begin与end相遇，交换此位置与keyi位置的值
	keyi = begin;
	return keyi;
}
void QuickSortNonR(int* a, int left, int right)
{
	//创建栈并初始化
	Stack SK;
	StackInit(&SK);

	//右左区间入栈
	StackPush(&SK, right);
	StackPush(&SK, left);

	while (!StackEmpty(&SK))//栈不为空，继续排序
	{
		int begin = StackTop(&SK);//取一组左右区间并出栈
		StackPop(&SK);
		int end = StackTop(&SK);
		StackPop(&SK);

		int keyi = Quicksort(a, begin, end);//调用快排hoare子函数

		if ((keyi + 1) < end)//如果右区间>1,入栈
		{
			StackPush(&SK, end);
			StackPush(&SK, keyi + 1);
		}
		if (begin < (keyi - 1))//如果左区间>1,入栈
		{
			StackPush(&SK, keyi - 1);
			StackPush(&SK, begin);
		}
	}
	StackDestroy(&SK);//排序完成，销毁栈
}

三、应用场景

1. 大数据排序：当需要处理大量数据时，快速排序能够高效地完成任务。由于它使用递归分治策略，因此能够很好地适应大数据集。

2. 文件排序：在需要按某种顺序处理文件中的记录时，快速排序可用于将文件内容排序。这对于数据库管理和文件索引尤其重要。

3. 内存数据库：在内存数据库中，数据通常存储在RAM中，以便快速访问。快速排序算法因其速度快，非常适合用于内存数据库中对数据进行排序。

4. 搜索引擎：搜索引擎在处理查询时，可能需要按相关度或其他指标对搜索结果进行排序。快速排序可以帮助搜索引擎快速地对大量搜索结果进行排序。

5. 实时数据处理：在需要实时处理大量数据的系统中（如实时分析、实时监控系统等），快速排序算法因其高效性而被广泛使用。

6. 编程竞赛和算法学习：由于快速排序算法是计算机科学中的经典算法之一，因此在编程竞赛和算法学习中经常被用作练习和评估学生或参赛者算法理解和实现能力的工具。

7. 操作系统：在操作系统的某些部分，如文件系统的元数据管理、进程调度等，可能需要对数据结构进行排序。快速排序因其高效性和稳定性，在这些场景中也有应用。

8. 图形和图像处理：在图形和图像处理领域，有时需要对像素、颜色或其他图像属性进行排序，以便进行进一步处理或分析。快速排序算法可以用于这些任务。

本文完

​