(排序5)快速排序(Hoare，选key的随机数与三数取中优化，挖坑法与前后指针法等)-Toy模板网

这篇具有很好参考价值的文章主要介绍了(排序5)快速排序(Hoare，选key的随机数与三数取中优化，挖坑法与前后指针法等)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速排序 (Hoare大佬版本)

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的单趟排序是这样的，首先是先要选出一个基准值/关键值key，然后再把这个数组当中所有比key小的数放到key的左边；再把这个数组当中所有比key大的数放到key的右边（弄完了之后，实际上也从侧面变相的说明：此时此刻key自己已经处在正确的位置上，也就是说排好序之后最终要去的位置）。
一般来说，这个基准值都是选择这个数组当中最左边的或者最右边的。
快速排序的单趟排序：快速排序的单趟排序也在排一个数，也就是说确定一个数的最终位置。但是他的单趟排序之外还附加了一个效果。就是说比key小的数在这么一次单趟排序之后全部在key所在位置的左边，比key大的数道理一样在右边。相当于还做了分割的这么一个功能。
关键结论：左边当key，让右边就先走；右边当key，让左边先走。这是一个结论，这样子做的目的就在于当左右指针相遇的时候，确保在相遇的这个位置的值是比key要小，正是因为有了这个确保，才可以进行交换。因此为什么需要这样？就是因为确保在相遇位置的那个值与key能够交换并且能够保证分割部分规律性不会破坏。
右指针找小，左指针找大，然后两者都到达既定位置之后，把两者所指向的位置的数给它调换一下。交换完了之后再继续向中间走。然后直到两个指针相遇，这时候就把相遇位置的数值与key进行交换。

//快速排序单趟排序
int keyi = left;
while (left < right)
{
	while (arr[right] > arr[keyi])
	{
		right--;
	}
	while (arr[left] < arr[keyi])
	{
		left++;
	}
	Swap(arr + left, arr + right);
}
Swap(arr + left, arr + keyi);

是上面这个写法吗?不是的，错误百出。排雷：当左右两个指针分别在进行找大与找小的操作的时候，不能直接在while循环判断条件里面单独大于号或者小于号，如果这样子的话可能会出现死循环。所以说都必须得加上等于号。这样子的话就可以说明，比如说我在找小的时候，我是真的在找小；找大的时候，我是真的在找大。也就是说比如说我的左右指针碰到了与key相等的情况，这时候就直接无视继续向中间走。在快速排序的单趟排序当中，我们知道规则就是说把比key小的数放到左边，然后比key大的数放到右边。至于那些与key相等的数的话，在左边右边都无所谓，因此当左右指针碰到与key相等的数的时候直接无视继续走，所以说等号必须得加到while循环的判断条件当中。这是第一点。
然后在里面的两个并列的while循环的判断条件里面必须得加上left＜right，不然会有大坑，因为这样的话，也在某些特殊情况的话会飘出去，会发生越界。正确代码为：

//快速排序单趟排序
int keyi = left;
while (left < right)
{
	while (left < right && arr[right] >= arr[keyi])
	{
		right--;
	}
	while (left < right && arr[left] <= arr[keyi])
	{
		left++;
	}
	Swap(arr + left, arr + right);
}
Swap(arr + left, arr + keyi);

快速排序的单趟排序完成之后，这时候key就已经不需要再去动了。接下来就是递归操作。这边声明一下：左指针的下标是left，右指针的下标是right，然后选中的关键值为key，关键值的下标是keyi
快速排序的单趟排序本质上也是在排一个数据，使那个数据key通过这个单趟排序落在正确的位置上。当单趟排序完成之后，接下来就是通过递归操作，需要递归两次。然后既然QuickSort是个递归函数，那么一开始在这个函数的开头必须得限制一下递归结束的条件。如果说当前这个数据段只有一个数据，那就没必要进行快排；或者说索性当前这个区间根本就不存在，那就更加没有必要进行快排。因此在函数开头得限定一下递归结束条件：left>=right，那么这时候就退出来。代码如下：

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

	//快速排序单趟排序开始
	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(arr + left, arr + right);
	}
	Swap(arr + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

快速排序的时间复杂度与优化的铺垫引入

假设在快速排序当中，以理想化的方式看待，就是说在每一个单趟排序完成之后，那个key就最终落在当前最中间的位置。
所有比key小的数落在他的左边，所有比key大的数落在他的右边。然后接下来就不断进行递归。然后你结合一下这个图，你会发现这个与二叉树非常的相似。在整个总的递归过程当中，大概有logN层。
然后在每一层当中，各个左右指针总共走的一个次数也大概都是在O(N)这个级别。虽然在实际上来讲，每一层的话左右指针总共走的次数肯定是在不断递减，因为随着越来越多的key值的最终正确位置被确定下来，所需要递归在处理的区间也在不断的缩小。但不管怎么样，由于时间复杂度统计的是一个量级，并不需要特别精确的计算。
因此总而言之，对于每一层而言，它的总共的遍历总数还是O(N)这个级别。再加上总共有logN层，所以说快速排序的时间复杂度为NlogN
而且根据图像我们可以发现，递归的深度为logN，这个就十分的友好，基本上不用考虑栈溢出的情况。因为就算这个n为100万，那么再加上log之后，也就变成了20左右，算个啥。
但上面讲的都是理想情况，接下来比如说举两个例子，当前需要排序的数组已经是升序有序或者降序有序，在这种情况下面执行上述快速排序代码的时候，根据图像可以发现此时它的递归深度为N，这就非常的隐患，当数据量一大的时候，非常容易发生栈溢出，因为他递归的深度不是之前理想情况下的logN，其次可以发现总的遍历的次数一个等差数列的相加，因此是O(N^ 2)。就算没有栈溢出的情况之下，N^2的效率也非常慢。
由此可以发现影响快速排序性能与递归深度的就是单趟排序之后key的所在位置。如果说在这个每次单趟排序之后，key总能够尽量的接近于中间位置，也就是说在递归的时候越能够进行二分，越二分的话就越接近满二叉数，越接近满二叉树的话深度就显得更加均匀，与此同时深度越均匀的话，效率也就越高。如果在当前的数据已经是有序或者说接近有序的情况之下。那么无论是递归的深度还是整个快速排序的效率都将会打折扣。（我这边都是默认在选择最左边当作key的情况之下）
因此，key的选取就需要优化一下，不能老是选择最左边的，不然会有效率低下与栈溢出的隐患。

快速排序（Hoare大佬版本 + 选key随机数优化法） (randi ----> left ----> 之前的逻辑)

因此归根到底就在于单趟排序之后key的所在位置
在快速排序当中没有硬性规定这个基准值到底必须在哪里。于是这时候有一种新的方法，就是说去随机的选key。
其实也相当于就是用生成随机数的方法，在生成随机数的同时必须得保证这个随机数一定是落在这个区间里面。为了保证生存的随机数一定是在参数的left，right这两个左右边界之内，于是生成随机数的时候不能直接rand()，要这样left + rand() %(right-left).
然后保持之前代码的逻辑不变，还是让最左边的那个值当key，不过并不是真正让原先最左边的那个字作为关键值，而是让新生成的随机数这个下标所在的值作为key，这时候就非常简单，只需要在随机数生成之后，把随机数指向的那个值与最左边的那个值交换一下就可以
在这种随机选key的情况之下，不管你原先是有序还是没有序，尤其假设原先你是有序的状态，但经过这么随机选key之后，就给他强行打乱了，至少这个key在单趟排序最终落在的位置是不这么靠近边边角角，那也就意味着更加接近于二分了。

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

	//快速排序单趟排序开始
	int randi = left + rand() % (right - left);
	Swap(arr + left, arr + randi);

	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(arr + left, arr + right);
	}
	Swap(arr + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

快速排序（Hoare大佬版本 + 选key三数取中优化法） (midi ----> left ----> 之前的逻辑)

还有一种选择key的方法就是三数取中，就是说把你当前这个需要排序的数组的头和尾巴拿出来，然后再把中间的那个值给他拿出来，然后三个数进行比较。然后选择那个既不是最大的也不是最小的那个值当成基准值。然后把基准值找到之后，我再跟最左边的换一下。这样子就又好比最左边的那个值就是基准值了，然后就接下来就可以套用原先的那个逻辑。
在原先这个数组是有序或接近有序的情况之下，三数取中优化会变得非常的棒。比随机数优化还要更加明显。
如果说原先这个数组也是随机的话，经过测试，总体而言三数取中还是比随机数优化要更加好一点。
对于三数取中与随机数优化取key而言，这时候这个快速排序基本上不存在最坏情况。我们说快速排序它的时间复杂度NlogN，但是实际上在某些特殊情况会跑到N^2这个级别，但是他还有的救，通过三数取中选key等优化就可以抢救一下。
所以说在快速排序当中不看最坏，不是因为搞特权，而是因为可以加优化，所以说快速排序的时间复杂度就是NlogN

int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);


	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(arr + left, arr + right);
	}
	Swap(arr + left, arr + keyi);
	//快速排序单趟排序结束

	keyi = left;
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

关于单趟排序中的为什么左边为key，要右指针先走的解释

之前有个关键的结论：就是说如果key选择最左边的那个数，那么左右指针必须是右指针先走，这样做的目的就是能够确保当左右指针相遇的时候，在相遇点那个值一定是比key要小（以升序排列为例），正是因为如此，就可以把相遇点那个值与key进行交换。如果说key选择最右边的，那么道理是一样的…接下来就解释一下具体的原因：
以最终目的升序排列为例，左边当key，右边先走，这样子就能保证最终相遇位置比key小；右边当key，左边先走，这样子就能保证最终相遇位置比key要大。
首先必须得知道就“相遇”而言，分为两种情况：第一种就是说是相遇前最后一幕：右边先走，因为右指针是找小，然后找到小之后就停下来不动了，然后左指针开始向右偏移去找大（每一轮都是右指针开始先走），但左指针找大没有找到，然后与右指针碰到了，这时候相遇位置的值很显然是比key要小。
刚才是左指针遇到右指针，有没有可能是右指针遇到左指针呢？也是有可能这个就是第二种情况。就是说相遇前最后一幕：就是说右指针不断向左偏移去找小，结果还没有找到直接碰到了左指针，这时候也可以去推断出左指针此时此刻指向的值更是比key小，因为在上一轮的交换过程当中，已经把比key小的值交换到此刻的左指针位置了，哪怕就是在最开始的话，无非就是最后直接到keyi位置，也就是key自己与自己交换。
所以说以升序排列为例：就是说如果key选择最左边的那个数，那么左右指针必须是右指针先走，这样做的目的就是能够确保当左右指针相遇的时候，在相遇点那个值一定是比key要小（以升序排列为例），正是因为如此，就可以把相遇点那个值与key进行交换。

快速排序（挖坑法，选key默认三数取中优化）

首先还是得搞清楚单趟排序的目的，就是把比key小的数赶到左边去，把比key大的数赶到右边去。
首先先把基准值保存到一个临时的变量当中，然后基准值所在的那个位置就形成了一个坑。然后右指针开始出发去找小，找到比key小的数之后就把它甩到那个坑当中，然后自己这边形成了一个新的坑；然后左指针开始向右偏移找大，找到之后甩到右边的那个坑里面，如此循环。然后左右指针一定相遇在坑里。
然后相遇的时候，把那个基准值放到那个最后那个两者相遇所在的坑里面。
挖坑法的话，相当于在原先的Hoare大佬方法的递归结构是保持不变的，只不过是在单趟排序的地方做了一些稍微改动而已。

int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);

	int hole = left;
	int key = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;

	QuickSort(arr, begin, hole - 1);
	QuickSort(arr, hole + 1, end);
}

快速排序（前后指针法，选key默认三数取中优化）

这种方法的话相当于用了一前一后的两个指针prev, cur ，或者说叫做下标。
首先就是cur一直往后走，然后当cur指向一个比key小的值的时候，先把prev++，然后把cur与prev位置上的值给他交换一下。然后cur++，总而言之cur是需要一直向右不断的走。
prev要么紧跟着cur（间隔为0，真一前一后），要么prev与cur中间间隔着比key大的一段值区间。然后到cur在不断向右走的过程中去找小，相当于就是把比key大的这段值区间感觉在不断的向右推，然后把比key小的数给他翻到左边去。
然后当cur不断向右偏移的时候，最终会超出原先的数据范围。然后对于prev有个规律，就是他的后面一个马上也就是比key大的数了，所以也就是说他本身指向的是比key小的数据。所以在最后，就是把prev所指向的数值与key进行交换。

int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] < arr[right] ? mid : right;
		}
	}
	else
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return arr[mid] > arr[right] ? mid : right;
		}
	}
}
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//快速排序单趟排序开始
	int midi = GetMidNumi(arr, left, right);
	Swap(arr + left, arr + midi);
	int keyi = left;

	int prev = left;
	int cur = prev + 1;

	while (cur <= right)
	{
		if (arr[cur] < arr[keyi])
		{
			prev++;
			Swap(arr + cur, arr + prev);
		}
		cur++;
	}
	Swap(arr + prev, arr + keyi);
	keyi = prev;

	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}