快速排序的原理及其多种方法的实现和优化

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

---

前言

本篇详细介绍了快速排序，让使用者对快速排序有进一步认识，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

---

一、快速排序介绍

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

 上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

二、快速排序实现的方法(升序）

1.hoare版本：

 思路图如下：

 我们先对单趟升序排序进行分析：

1.从右边先走（后面会解释），右找比key小，找到停止，否则继续向左前进

2.右边停止后，左边开始找比key大的，找到停止，否则继续向右前进

3.两边都停止时，且未相遇，则交换

4.相遇时，则将下标为key与下表为left的值进行交换，此时key到达正确位置

void PartSort1(int* a, int left, int right)
{
int keyi = left;
int begin = left;
int end = right;
while (left < right)
{
	if (left < right && a[right] >= a[keyi]) //避免数组内找不到导致left或right无法停止
	{
		right--;
	}
	if (left < right && a[left] <= a[keyi])
	{
		left++;
	}
	Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
}

 现在我们对已经找到key的正确位置了

此时数组内可分为

对begin到keyi-1的数据我们也可以看作一个完整的数组，这样将大问题分成小问题解决，我们就利用递归来解决这道问题。

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
void PartSort1(int* a, int left, int right)  //升序左找大右找小；
{
	if (left >= right) // 区间只有一个值或者不存在就是最小子问题
	{
		return;
	}
	int keyi = left;
	int begin = left;
	int end = right;
	while (left < right)
	{
		if (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		if (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	PartSort1(a, begin, keyi - 1); //递归左
	PartSort1(a, keyi + 1, end); //递归右
 
}

 到这里我们代码基本完成

很多人想问，为什么一定要从右边开始找呢？

 

2.挖坑法

思路图如下：

 这个思路核心仍然是hoare的方法，但不需要区分左走还是右走，更便于教学理解

代码如下：

int PartSort2(int* a, int begin, int end)
{
	//begin是坑
	int key = a[begin];
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;
 
		// end给begin这个坑，end就变成了新的坑。
		a[begin] = a[end];
 
		while (begin < end && a[begin] <= key)
			++begin;
 
		// end给begin这个坑，begin就变成了新的坑。
		a[end] = a[begin];
	}
 
	a[begin] = key;
 
	return begin;
}

3.前后指针法 

核心

1.cur>=key,cur++

2.cur<key,++prev,交换prev和cur的值，cur++

 prev和cur的关系：

1. prev紧跟cur一前一后

2.prev和cur之间是比key大的值

根据这些以及递归思想，我们可以写出如下代码 

void PartSort3(int* a, int left, int right)
{
	if (left >= right) // 区间只有一个值或者不存在就是最小子问题
		return;
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	PartSort3(a, left, keyi - 1);
	PartSort3(a, keyi + 1, right);
}

 三、快速排序的优化

1. 关于所排序的数据有序或接近有序的问题

假设我们得到一个有序或者接近有序的数据，利用我们之前写的快速排序，我们会发现快速排序却不如时间复杂度高的排序方法，这是为什么呢？

如图所示，在数据有序的情况下，我们每一次都 要遍历整个数组来确定key的位置，时间复杂度达到了O（N^2),这显然不能符合他的“快速”

因此我们要对此进行优化

1.1 随机取key方法

在有序问题中，我们发现取key基本上是最小或最大的数值，导致left基本不懂，right几乎每次都要到数组靠前的位置，因此，我们如果取的key为随机呢。

void QuickSort1(int* a, int left, int right)
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
    int begin = left, end = right;
	//选[left, right]区间中的随机数做key
	int randi = rand() % (right - left + 1);
	randi += left;
	Swap(&a[left], &a[randi]);
    int keyi = left;
	while (left < right)
	{
			// right先走，找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}
 
			// left再走，找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}
 
			Swap(&a[left], &a[right]);
		}
 
		Swap(&a[left], &a[keyi]);
		keyi = left;
 
		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
}

1.2 三数取中法

顾名思义，就是取key为[left,right]区间内的中间值

取中代码如下：

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
 
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

整体代码如下：

void QuickSort1(int* a, int left, int right)
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
	int begin = left, end = right;
		// 三数取中
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;
	while (left < right)
	{
			// right先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
 
			// left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
 
			Swap(&a[left], &a[right]);
		}
 
		Swap(&a[left], &a[keyi]);
		keyi = left;
 
		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
}

 

2.关于递归深度过深导致栈溢出问题 

2.1 利用栈实现非递归结构

#include"Stack.h"
void QuickSortNonR(int* a, 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 = begin;
		int cur = begin + 1;
		int prev = begin;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[cur], &a[prev]);
			cur++;
		}
		Swap(&a[keyi], &a[prev]);
		keyi = prev;
		// [begin, keyi-1] keyi [keyi+1, 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);
 
}

2.2 小区间优化

快速排序在大量数据的处理上有着显著的优势，但在小区间内的排序速度有时却不如插入排序等时间复杂度高的排序.

快排递归到小区间时，我们可以采用插入排序进行优化，减少递归次数，提速和减少空间利用。

代码如下

if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
	}

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解了数据在内存中的存储，如果对你有帮助给个