C语言植物大战数据结构快速排序图文示例-C/C++开发

这篇文章主要为大家介绍了C语言植物大战数据结构快速排序图文示例，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。所以快速排序有种方法是以他的名字命名的。相比70年前的祖师爷级的大佬来说，今天我们学习快速排序的成本已经非常低了。今天的我们的是站在巨人的肩膀上学习快速排序。

快速排序有三种方法实现，我们都需要掌握。

一、经典1962年Hoare法

让我们来看看1962年祖师爷发明的快排吧。

什么是快速排序？给你以下代码，请你完善快速排序，你将怎么完善？

快速排序：顾名思义，它比较快，整体而言适合各种场景下的排序。缺陷相较于其他排序小。且大部分程序语言排序的库函数的源代码都是由快速排序实现的

void QuickSort(int* a, int left, int right)
{
	//请你完善以下代码
}
int main()
{
	int arr[] = {6,1,2,7,9,3,4,5,10,8};
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

具体实现：

Hoare法和二叉树的**前序遍历(根左子树右子树)**简直一模一样。

整体思路：

1.先进行一趟排序。

2.进行左半区间(左子树)递归。

3.进行右半区间(右子树)递归。

1.单趟排序

所有的排序的思想：就是先考虑单趟的排序，再合成n躺排序。这是毋庸置疑的，因为这样的思想很自然。

对于单趟排序，也有一个思路。可以说算是规定吧，这是祖师爷Hoare的规定。

为了好理解思路，以下思路是整体上的思路，写出来的程序还是有bug的。具体细节需要后期修改。

一定要按照规定走哦，不要问那么多为什么。按照规定走你就知道为什么要这么做了。总体思路规定：

1.设置一个基准值key，key一般为左边第一个数的下标。定义左指针left和有指针right分别指向第一个和最后一个。

2.先让右边的right指针往左走，一直找比key所指向小的数，找到后就停下。

3.紧接着让left指针往右走，一直找比key所指向大的数，找到后就停下。

4.如果第2步的right和第3步left都找到了，则交换swap两者的值。然后继续循环2和3步，直到left >= right为止。

5.此时left = right, 交换left和right相遇的位置的值与 key位置上的值。

此时，Hoare 的单趟排序完成。产生的效果是key作为分割线，把大小分割开了，比key所指向值小的在key左边，比key所指向值大的在key右边。

2.递归左半区间和右半区间

对于单趟来说。

单趟排完之后，key已经放在正确的位置了。

如果左边有序，右边有序，那么我们整体就有序了。

那左边和右边如何有序呢？

解释：分治解决子问题。相当于二叉树。

一趟排序完成后，再对左半区间进行单趟排序，一直递归到什么时候结束呢？

解释：递归到左半区间只有一个值的时候，或者为空的时候递归结束。

这个过程适合用画递归图来查看。

由于数据是10个数，递归图庞大。所以此处省略。下面双指针法有具体递归图。

3.代码实现

具体代码实现和你想的总是那么不同。因为特殊情况确实是存在，且还是那么离谱。

我认为这个题难在了边界问题，边界问题要时刻注意！。

特殊情况1：当排以下数据时，我只是把6改了，这样会导致right和left直接不走了。

{6,1,2,7,9,3,4,5,10,6}

特殊情况2：当排以下数据时，会发生left找不到最大的值导致越界。

{5,4,3,2,1}

改动如下。

//快速排序Hoare
int PartSort(int* a, int left,int right)
{
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			--right;
		}
		while (left < right && a[left] <= a[key])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[key]);
	return left;
}
void QuickSort(int* a, int left, int right)
{
	//当有个区间为空的时候right-left会小于0。
	if (right <= left)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div-1);
	QuickSort(a, div+1, right);
}
int main()
{
	int arr[] = {6,1,2,7,9,3,4,5,10,8};
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

二、填坑法(了解)

和Hoare法思想类似，大差不差，没什么区别。相比Hoare法较好理解。因为挖坑填坑思想很生动形象，所以较好理解。

1.单趟思路

单趟思路：

1.先保存key的值。让左边的key做坑(pit)，让右边找比key小的，然后填到坑中。

2.然后让那个小的做坑，再让左边找比key大的，找到后填到坑中。依次循环，直到right和left相遇。

3.相遇后，把key的值填到相遇的位置。

这时，单趟循环结束。

2.代码实现

和Hoare法相似，只是少了交换的步骤。注意：要事先把key的值保存下来。

int PartSort(int* a, int left, int right)
{
	int keyval = a[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && a[right] >= keyval)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= keyval)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = keyval;
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, sz-1);
	return 0;
}

三、双指针法(最佳方法)

1.单趟排序

和以上两种方法的不同之处只有单趟排序，也就是PartSort函数的部分.

优点：有了双指针的优化，不需要考虑边界问题！写代码不易出错。

代码好写，不好理解。代码极为简单，只需五行。

双指针法也称快慢指针法，两个指针一前一后

2.具体思路

对于排6,3,2,1,5,4的升序来说。

思路：让cur找比key指向的值小的，找到后，++prev，交换prev和cur位置的值。若cur比key指向的值大，则不交换。

prev和cur的关系：

1.cur还没遇到比key大的值时，prev紧跟着cur，一前一后。

2.cur遇到比key大的，prev和cur之间的一段都是最大的值

第一趟排序后的结果。这时候div为基准值。将左右子树分隔开。

全部排完序后的二叉树图。

3.代码递归图

红色线代表递归，绿色线代表返回。

4.代码实现

#include <stdio.h>
void Swap(int* x, int* y)
{
	int t = 0;
	t = *x;
	*x = *y;
	*y = t;
}
int PartSort(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = left + 1;
	//推荐写法一，较好理解
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	//写法二。比较妙，不好理解
	//while (cur <= right)
	//{
	//	if (a[cur] < a[key] && a[++prev] != a[cur])
	//	{
	//		Swap(&a[cur], &a[prev]);
	//	}
	//	++cur;
	/