【初阶数据结构与算法】一命通关“快速排序“（内含快速排序的三个版本以及非递归）

埋头编程

发布于 2024-10-16 19:03:43

790

发布于 2024-10-16 19:03:43

文章被收录于专栏：C/C++

前言

无论是我们学过的插入排序、希儿排序、选择排序、冒泡排序以及堆排序，这些在我们实际做项目时都不算很常用，那么本文给大家介绍一个牛犇的排序 —— “快速排序”。正如名字一样朴实无华，但是它确实排序的效率很高（将于快速排序的优化版本）。

在本文中，我会给大家详解快速排序的三大版本，以及优化快速排序的思路，还要给大家讲一下作为一个合格程序员必须得做到的一些技能。

好了，我就不卖关子了。让我们开启快速排序的冒险之旅吧！！！🚢🚢⚓

1. 快速排序的单趟排序 - 算法思想（十分重要）

在我们开始写代码时，理解算法的思路是不可或缺的一部分，所以接下来我们就来理解一下快速排序的算法思想。（我们算法讲解的思路都是以升序排序的为主。相信大家也知道一件事，只要我们弄懂了升序，那降序肯定也不在话下）

核心思想：在待排序的数组中，我们要选择一个值，这个值我们通常称其为key值。这个key值的选择是会影响快速排序的效率的，这个点后面会说。随后我们会定义两个变量left和right，控制待排序数组的区间。下面最核心的来了！我们假定待排序数组的第一个元素就是key值，此时我们一定要让right变量先动（这个点后面会解释），right变量往前动起来的目的就是为了找比key值小的数。之后我们再让left变量往后动起来，left变量往前动起来的目的就是为了找比key值大的数。然后，将这两个数进行位置上的交换。这个过程一直持续到当right和left相遇时，此时就得将key值一开始所在的位置与相遇位置的值进行互换，最终达到的效果是比key值小的数都在key值的左边，比key值大的数都在key值的右边。以上就是快速排序的单趟排序思路。

如果你觉得上述的文字解释有点难以理解的话，没有关系，可以再看一下下面的图文讲解（附带例子的图文讲解）：

基于上述的例子我来给大家做一个详细的步骤拆解。

最终效果：

到这里，快速排序的单趟排序的思想就讲解完毕了！！！

接下来就进入用代码实现上述的思想的环节了。

2. 快速排序的单趟排序 - 代码实现

其实上述我们讲解的思路，就是发明该算法的人提出的，此人名为hoare。提前透露一下，这个版本的代码理解起来不是很容易，而且书写容易出错，出错的点首先就是在选最左边的值为key时得让right先走。为此，后面又出来了挖坑法、以及前后指针法（这个又是另一种玩法思路了）。那么在本小节中，我会给大家逐一击破！

2.1 hoare版本

在此之前，我们还是得膜拜一下hoare大佬，学习他的版本。

这里我就不过多阐述思想了，直接上代码：

void QuickSortPart1(int* a, int left, int right)
{
	//hoare版本 - 单趟排序

	//我们选择最左边为key值，这里我们可以采用记录下标的方式。
	int keyi = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= a[keyi]) //right < left这一步是为了不让right和left越界
		{
			--right;
		}

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
		Swap(&a[left],&a[right]);
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	Swap(&a[left],&a[keyi]);
	keyi = left;
}

大家可能在理解上述思想的基础上，写这段代码时可能有一些细节没有处理到位，导致预期不一样，这个就是hoare版本的一个弊端了。

具体会有哪些出错的地方呢？

将这个 aright >= akeyi 和这个 aleft <= akeyi分别写成了aright > akeyi 和 aleft < akeyi，甚至只有一个循环加了等号里一个没有加，这个就是错误的原因之一。另外还有一个就是，right和left越界了没有判断，从而会导致程序崩溃！

好了，大家会发现hoare大佬的这个版本的思想非常不容易理解。后来，人们就根据hoare大佬的思想研发了另一种方式——“挖坑法”。

2.2 挖坑法

这个方法的底层就是hoare大佬的思想。

🍉可以看到上面的动图，当我们在选取的key值的时候，就相当于在这个位置上面挖个坑，我们可以用一个变量记录此时坑出现的位置。然后按照hoare大佬的思想，将需要移动数据移动到久坑，那么此时就会出现新的坑，我们更新记录坑这个位置的变量即可。

void QuickSortPart2(int* a, int left, int right)
{
	//挖坑法版本 - 单趟排序

	//我们选择最左边为key值，这里我们就直接采用记录值的方式。
	int key = a[left];

	//定义一个坑
	int hole = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= key) //right < left这一步是为了不让right和left越界
		{
			--right;
		}
		//找到了新的坑了,先把旧坑填了
		a[hole] = a[right];
		hole = right;

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= key)
		{
			++left;
		}

		//找到了新的坑了,先把旧坑填了
		a[hole] = a[left];
		hole = left;
		
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	a[hole] = key;
}

2.3 前后指针

除了hoare大佬这个思想之外，有人还提出了一种新的思想 —— “用前后指针来实现”。但不论是hoare这个思想还是前后指针的做法，其本质就是将待排序的数组分割成两个子区间，这两个子区间的特点就是其中一个子区间里面的元素都大于基准值（key值），另一个子区间里面的元素都小于基准值（key值）。

那这个前后指针是如何做到上述的思想的呢？大家可以先看下面的动图：

可以看到的是：

它会分为两种情况：

当key值大于cur指向的值时，先让prev往后走一步，紧接着，再让 prev位置上的值与cur位置上的值交换位置。最后，cur再往后面走一步；
当变量cur所指向的值大于key值时，直接让cur往后面走一步即可。

这个思想的原理就是，通过key值与cur所指向的值的关系，控制prev的指向，使得比key值大的数不断地往数组后面逼近。

上代码：

void QuickSortPart3(int* a, int left, int right)
{
	//前后指针版本 - 单趟排序

	int n = right - left + 1;
	//我们选择最左边为key值，这里我们就直接采用下标的方式。
	int keyi = left;

	//定义一个prev和cur
	int prev = left;
	int cur = left + 1;
	
	while (cur < n)
	{
		if (a[keyi] > a[cur])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}

		cur++;

	}

	Swap(&a[prev],&a[keyi]);
	keyi = prev;
}

好了，至此，关于快速排序单趟排序的三个版本的代码演示就完成了！！！

2.4 三个版本我该改用哪一个？

这个问题相信有很多读者会提出疑问，这三个版本都能实现同一个功能，那我能不能偷懒只了解一种呢？

答案肯定是不行的。

如果你实在记不住那么多的话，强烈推荐前后指针这个版本。这个版本也是现在很多人写快速排序算法时会用到的方法。

除了这个之外，我们以后找工作肯定会有面试，这个难免会碰到面试官会问你这个问题，所以建议大家都要掌握！！！

3. 快速排序的整体排序

3.1 快速排序的整体排序的算法思路

从单趟排序我们就可以知道，单趟排序的目的就是将我们所选的key值放到待排序数组中正确的位置上。然后就将待排序数组划分成两个区间begin, keyi-1 keyi keyi+1,end。然后，我们又可以对这两个区间里的值再使用单趟排序的思路，这个不就是妥妥的递归！！！

如果你还不理解，请看下面的图：

3.2 快速排序的整体排序的代码实现

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

	int begin = left, end = right;

	//hoare版本 - 单趟排序
	//我们选择最左边为key值，这里我们可以采用记录下标的方式。
	int keyi = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= a[keyi]) //right < left这一步是为了不让right和left越界
		{
			--right;
		}

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
		Swap(&a[left], &a[right]);
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	Swap(&a[left], &a[keyi]);
	keyi = left;

	//递归
	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi + 1, end);

}

有了上面的思想，递归看起来也不是很难理解吧！！！

4. 找key值的方式

我们为什么要谈论这个问题呢？相信大家在上面已经察觉到了，我们的key值目前来说要不就是去待排序数组开头的元素，要不就是待排序数组结尾的元素。那这样做不会有问题吗？

🍉🍉🍉那本小节我们就来解开这个谜底！！！

4.1 为什么要提出找key值的方式？

有一部分的读者会认为：哎呀，我直接选待排序数组开头的元素，要不就是待排序数组结尾的元素作为key值挺好的啊，我能够理解hoare大佬的思想。

可以想一下快速排序的时间复杂度是多少？

不难看到应该是O(N*logN)。

但是大家有没有想过这么一个问题：我们用刚才写的快速排序来排一个已经有序（升序、降序）的数组的是将复杂度又是多大呢？

可以看到它的时间复杂度变为了O(N^2)。这个时间复杂度对于排序算法来说是个大忌啊！！！我们有什么办法能够抢救一下这个时间复杂度吗？方法肯定是有的。

可以看到时间复杂度之所以这么高，是因为keyi的位置所导致的。总结上面的思想，我们希望看到的是keyi值越是取整个待排序数组中较为中间的值时，它的效率是最大的，为什么呢？你可以想一下，如果keyi所在位置的值是待排序数组的较为中间的值，那么经过一次单趟排序后，其分出的两个子区间各自的元素数量较为均等，我们这样就越接近logN这个量级，而不是N这个量级了。

所以人们就提出了两种选择key值的策略：

随机数选key
三数取中

那它们具体是如何实现的呢？请看下面的讲解。

4.2 随机数选key

这个方式我不是很推荐大家使用，不过这个方法现在仍有人在玩！

随机数选key的代码很简单就是利用rand函数生成一个区间范围内的数，将它与最左边或最右边的值互换。

可能有的读者就会问了，为什么要互换呢，我直接选了就直接用不好吗？

这里要说明的一点是，肯定是要交换位置的！！！原因是承接我们上面代码的思想。

void QuickSort(int* a, int left, int right)
{
	srand((unsigned int)time(NULL));
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;

	//hoare版本 - 单趟排序
	//我们选择最左边为key值，这里我们可以采用记录下标的方式。

	//随机数选key
	int randi = left + rand() % (right - left + 1);
	Swap(&a[randi],&a[left]);

	int keyi = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= a[keyi]) //right < left这一步是为了不让right和left越界
		{
			--right;
		}

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
		Swap(&a[left], &a[right]);
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	Swap(&a[left], &a[keyi]);
	keyi = left;

	//递归
	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi + 1, end);

}

4.3 三数取中

选取的三个数字分别位于待排序数组开头位置的元素、中间位置的元素以及结尾位置的元素

代码如下：

//三数取中
int GetMidNum(int* a, int left, int right)
{
	int mid = (left + right) / 2;

	if (a[left] > a[right])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else //说明a[mid]<=a[right]
		{
			return right;
		}
	}

	else//说明a[left]<=a[right]
	{
		if (a[left] > a[mid])
		{
			return left;
		}
		else//说明a[left]<=a[mid]
		{
			return mid;
		}
	}
}

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

	int begin = left, end = right;

	//hoare版本 - 单趟排序
	//我们选择最左边为key值，这里我们可以采用记录下标的方式。

	//三数取中
	int midi = GetMidNum(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi],&a[left]);
	}
	int keyi = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= a[keyi]) //right < left这一步是为了不让right和left越界
		{
			--right;
		}

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
		Swap(&a[left], &a[right]);
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	Swap(&a[left], &a[keyi]);
	keyi = left;

	//递归
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

这样我们就能很好的解决快速排序时间复杂度为O(N^2)的问题了。

5. 快速排序的非递归

我们都知道如果递归深度过深时，会导致栈溢出的情况，从而使整个程序崩溃。

所以我们就必须具备一种能力，将递归改为非递归。

将递归改为非递归有两种方式：

直接改造成循环（就先斐波那契数列一样）；
利用栈这个数据结构来实现。

我们在这里用的时第二种方式，如果有对栈这个数据结构还不理解的读者，可以去看一下我往期的文章详解栈和队列。

这里我们可以这么想，我们通过单趟排序使得区间划分成了两个部分，然后我们在对这两部分区间再次使用单趟排序的思想。所以这里的关键就在于区间的划分，我们可以使用栈先将我们要后排序的区间先入栈，先排序的区间最后在入栈。

代码的实现如下：

int QuickSortPart(int* a, int left, int right)
{
	//hoare版本 - 单趟排序
	//我们选择最左边为key值，这里我们可以采用记录下标的方式。

	//三数取中
	int midi = GetMidNum(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi], &a[left]);
	}
	int keyi = left;

	while (left < right)
	{
		//先让right动，因为我们选取的是左边的key
		//right的目的是找到比key值小的元素的位置
		while (right > left && a[right] >= a[keyi]) //right < left这一步是为了不让right和left越界
		{
			--right;
		}

		//之后在让left动
		//left的目的是找到比key值大的元素的位置
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
		Swap(&a[left], &a[right]);
	}

	//出了while循环后，就说明了此时left=right。那我们就得将此位置上的数与keyi上面的数进行交换。
	Swap(&a[left], &a[keyi]);
	keyi = left;

	return keyi;
}

void QuickSortNonR(int* a, int left, int right)
{
	
	Stack st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = QuickSortPart(a, begin, end);

		if (keyi + 1 < end)//用来判断右子区间
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}

		if (keyi - 1  > begin) //用来判断左子区间
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	
	STDestory(&st);
}

到这里，本文的内容就全部讲完了。如果你觉得有所收获的话，麻烦给偶点个赞吧！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

排序