【数据结构】第十三站：排序（中）快速排序

一、快速排序递归法

1.快速排序思想

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

2.hoare版本实现快速排序

hoare版本的快速排序的基本思路是，先选出最左边或者最右边的值为key，如果选左边，那就让右边先走，如果选右边，那就让左边先走。后面会说为什么必须这样走。我们假定选左边为key，那么当右边碰到比key小的时候，停下来。然后让左边走，当左边的找到一步比key大的时候，左边停下来，然后交换这两个值。
之后，我们将循环结束的位置称之为keyi，这样，我们交换key和keyi位置的数据。
然后这样我们会发现，我们已经将一个数据给放到他应该在的位置上了。
这样我们可以使用递归的思想，将左半区间和右半区间分别递归。
如此一来。也就成功实现了排序

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	QuickSort(a, begin, left - 1);
	QuickSort(a, left + 1, end);

}

如上代码所示，但是这种方法我们需要有几点注意事项
1：递归结束条件，不难发现，我们这样一直递归下去，总有一个区间只有一个元素，或者不存在元素。这样的情况就得返回了。由于我们是知道left和right的，一旦上一层递归中只有两个或者三个元素的时候，下一次递归传递的left和right一定是left>=right的。这就可以作为递归结束条件了。
2.右边找小和左边找大的时候，假如不添加left<right进行限定。那么一旦整个数组的其他值都大于key，或者小于key，有可能造成直接越界了。
3.我们所说的找小和找大是严格的小于，不能是等于，因为等于可以是在key的左边也可以是在key的右边，如果我们特殊处理等于的情况，有可能造成无法预知的后果。
4.如果选左边为key，那么必须从右边开始走，反之亦然。只有这样才能保证相遇位置一定是小于key或者大于key的一个数。后面会详细证明

时间复杂度分析
对于上面的快排，我们可以简单的分析一下时间复杂度。不难得知，他的递归方式类似于一颗二叉树。
不难发现，他最好情况一共有logN层，第一层有一个key，每一侧的key都是上一层的两倍。但是当数据量很大时候，key的数量对N的影响不大。所以每一层的数据量仍然是O(N)级别，而每一层我们其实都会遍历一遍的为了选出同key数量相等的数。所以每一层的时间复杂度为O(N)。所以总的时间复杂度为O(N*logN)，而空间复杂度为O(logN)，这是因为总共会开logN层栈帧。
但是上面的其实是最好的情况，对于快排而言，最坏的情况是数据量全部顺序，或者全部逆序的情况。在这种情况下，快排由于每次只能搞定一个元素，而这个元素恰好就是最边缘的元素，这样就需要开N层栈帧，每层都需要N-i次，类似于等差数列。时间复杂度变为了O(N²),空间复杂度变为了O(N)。

3.hoare版本的优化

我们可以看到hoare版本的快速排序其实还是存在一些问题的，当数据顺序或逆序的时候，效率很低。反而乱序的时候效率很高。所以我们可以采用一些特殊方法来处理一下。

1>使用随机值rand()函数

我们发现，快速排序的问题就在于一旦出现顺序或者逆序就会导致效率很低，但是我们可以使用一种随机选key来处理一下。使得每一次选出的key都是随机值，具体做法为使用rand函数，随机生成一个下标，将这个下标与最左边的交换。这样就能确保每一次都是一个随机的下标。因为在大量数据面前，每次随机选数，恰好为顺序或逆序的概率为0。根据这种思想，代码为

//快速排序
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left;
	int randi = left + rand() % (right - left);
	Swap(&a[randi], &a[left]);
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);

}

2>三数取中

三数取中的基本思想是这样的：将最左边，最右边，以及中间三个位置的元素的数据中，取出中间的数据，然后让数值为中间的数据的下标与最左边进行交换，而取中的逻辑可如下
>由于三数取中的优化，可以使得每一次的左值一定不是最大或者最小的。从而优化掉顺序或者逆序的情况

int GetMidNumi(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 right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}
//快速排序：三数取中
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left;
	
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	QuickSort2(a, begin, left - 1);
	QuickSort2(a, left + 1, end);
}

3>三路划分

如果遇到大量相同的元素的话，那么前面的方法都不好使了。这时就引出了三路划分。三路划分后面具体详细讲解

4.证明hoare版本的key在左边，必须让右边先走

左边做key，必须右边先走，可以保证相遇位置一定小于key或者相遇位置就是key，从而使得key与相遇位置交换后，使得key落到他应该存在的位置。

1.R找到小，L找大没有找到，L遇到R，相遇位置一定是比key小的

2.R找小，没有找到，直接遇到L,要么就是一个比key小的，要么就是直接就是key

3.类似道理，右边作key，左边就得先走

5.挖坑法实现快速排序

首先是挖坑法的基本思想，先将最左边的数保存在一共临时变量里面，然后让这个左下标设置为坑，假定坑内没有有效数据，然后右边先走，当遇到一个比临时变量小的数的时候，将这个值甩给坑，然后将坑重新设置为当前的right。然后左边走，找到一个比临时变量大的数据的时候，将这个数据甩给右边的坑。如此循环下去。当两个相遇的时候，我们在将临时变量的值赋给坑。就将一个数据排好了

//快速排序：挖坑法
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int hole = left;

	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	int key = a[left];
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	QuickSort3(a, begin, hole - 1);
	QuickSort3(a, hole + 1, end);
}

6.将前面快排的一趟排序给提取出来

这是为了方便我们后面写快排的非递归形式.

int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}
int PartSort2(int* a, int left, int right)
{
	int hole = left;
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	int key = a[left];
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort2(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

7.双指针法实现快速排序

双指针法的基本思路如下：
1.仍然让最左边设置为key，然后让prev指针指向第一个元素，让cur指针指向第二个元素。
2.当cur所指向的小于key的时候，我们先让prev++，然后让prev所指向的与cur所指向的交换位置。然后让cur++。
3.当cur所指向的大于key的时候，我们直接让cur++即可。
4.最终当cur大于right的时候结束。此时prev恰好指向最后一个小于key的数，prev后面的全部数都是大于key的。
5.我们直接让key和prev进行交换。这样就将一趟给排好了

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	int prev = left;
	int cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] > key)
		{
			cur++;
		}
		else
		{
			prev++;
			Swap(&a[prev], &a[cur]);
			cur++;
		}
	}
	Swap(&a[prev], &a[left]);
	return prev;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

事实上，上面的代码还有一种更加优雅的写法

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	Swap(&a[midi], &a[left]);
	int prev = left;
	int cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[prev], &a[left]);
	return prev;
}
//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

8.快速排序小区间优化

由于我们的快速排序是使用递归的思想。类似于二叉树。我们可以发现，在最底层的递归中。每一个都是小区间，但是每一个小区间我们都需要使用很多次递归。而最后的几层占据了绝大多数递归。比如最后三层，占据了50%+25%+12.5%=87.5%的递归。这样的消耗确实挺大。我们可以在最后的小区间，让他不要使用递归了，直接使用插入排序来进行优化。因为小区间以及很接近有序了。使用插入排序最佳。这样可以极大的节约消耗。当然区间不可以太大，因为我们要考虑小区间直接插入的效率高于递归的效率，否则得不偿失

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if ((right - left + 1) > 10)
	{
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
}

二、快速排序非递归

上面我们已经详细分析了快速排序的递归版本。但是只要是递归就一定会存在某些问题：
1.效率
2.深度太深，栈溢出
这时候就需要我们将递归形式改为非递归形式。

递归改成非递归有两种情况
1:直接改递归，这比较适合一些简单的递归
2:间接改递归，使用栈辅助改递归

对于这个快排，我们直接改递归是比较困难的，我们可以使用间接的方式
递归其实就是不断建立栈帧的过程，而栈是可以模拟一个递归的过程的
我们先分析在递归下的快排，其实快排递归本质就是区间的变化

我们可以将他的区间下标给入栈，为了更好的模拟，我们需要使用右边的变量先入栈，然后再让左边的变量入栈。这样可以保证最终先出的是左边的，然后是右边的变量。我们每次入区间的时候，也是先让右区间入，再让左区间入，这样可以保证出的时候先出左区间。
然后就是我们不断取出区间，进行每一趟快排了，这也就是之前我们需要将一趟快排给提取出来的原因，为了方便我们改为非递归。后面就是不断入区间出区间的过程了

//快速排序非递归
void QuickSortNonR(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	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 = PartSort3(a, begin, end);

		
		// [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);
}

———————————————————————————————————————
好了本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！文章来源地址https://www.toymoban.com/news/detail-428318.html

到了这里，关于【数据结构】第十三站：排序（中）快速排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！