排序——快速排序

思想

演示

代码实现

解释

优化

三数取中

小区间优化

补充

挖坑法

双指针法

非递归实现

思想

快速排序是一种二叉树结构的交换排序方法。

基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

演示

一般把序列的第一个元素认为基准值。定义两个变量一个是序列最右边一个是最左边（变量均为下标）。

先让end走遇到比基准值小的停下来，然后让begin走遇到比基准值大的停下来，之后让它们交换位置。一直重复操作直至它们相遇。

当它们相遇时，该位置的值一定小于基准值（在后面的解释中会有说明）。让该位置的值与基准值交换。

以上是一遍排序，还要继续排序下图的浅绿色序列和亮绿色序列，操作是和这次一样的只是范围不一样。在排完之后会继续再分用递归解决即可。

大概流程图如下：

大家不能只看我画的图，也要自己画画图感受感受。

代码实现

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;

	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		while (begin < end && arr[end] >= arr[keyi])
			end--;
		while (begin < end && arr[begin] <= arr[keyi])
			begin++;

		Swap(&arr[begin], &arr[end]);
	}

	Swap(&arr[keyi], &arr[end]);

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

Swap函数是交换两个数。

void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

解释

end遇到begin：

begin没移动：那就是自己给自己交换一下位置。
begin移动了：begin经历了交换它下面的值一定小于基准值。

begin遇到end：因为end先走，end停下的位置一定小于基准值。

这也就解释了为什么要让end先走，如果要让begin先走那可能就不会当它们相遇时该位置的值一定小于基准值。

优化

三数取中

快速排序的理想时间复杂度是O(NlogN)，理想情况每次左右序列的长度相同时存在。如果该序列是有序或接近有序那时间复杂度就是O(N^2)如下图。这样快速排序的效率就会大打折扣。为了避免这种情况有人提出了三数取中。

三数取中就是在序列中拿首元素，序列正中间的元素，尾元素这三个元素中挑一个中间元素来当基准值。这样做尽量保证每次的左右序列的长度相同，让它向理想情况靠近。

当选出来时让该位置与序列首元素交换位置这么做是保证我们之前的逻辑。

//三位取中
int GetMidi(int* arr, int left, int right)
{
	int midi = (left + right) / 2;
	if (arr[left] < arr[midi])
	{
		if (arr[midi] < arr[right])
		{
			return midi;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[midi] > arr[right])
		{
			return midi;
		}
		else if (arr[left] > arr[right])
		{
			return right;
		}
		else
		{
			return left;
		}

	}
}

小区间优化

在上面提到过快速排序是一种二叉树结构的交换排序方法。

它是一个二叉树结构，根据二叉树特点可知最后一层开辟的空间会约占全部的50%，它的上一层约占到25%。如果数据很多那么递归调用的深度就会很深有可能造成——栈溢出。

最后的一两层里面包含的数据并不是很多，所以我们可以写一个判断，到特定的范围内用插入排序的方式来排序（这里我写的是当数据量小于10时），这样它的深度会变小很多。

补充

挖坑法

这是针对排一遍方法的改进下面的双指针法也是一个道理。

将第一个数据存在一个临时变量key中，从而形成一个坑位。让end先走当遇到比key小的数据时把end位置的值放入坑中，end位置就会形成一个坑。然后让begin走遇到比key大的就把它放入坑中。一直重复操作直至它们相遇。

最后它们相遇时把key放入它们相遇位置即可。

双指针法

先定义两个变量一个指向序列的首元素(prev)，一个指向首元素的下一位(cur)。

如果cur对应的值大于key（序列首元素），那就让cur独自向后走。如果小于key，让prev向后走然后让cur和prev交换位置如果cur等于prev那就不需要交换位置（下图是一部分移动过程）。

当cur走出序列后，让prev与key进行交换。

prev是在cur对应的值小于key的情况下才走固prev对应的值一定小于key。

非递归实现

快速排序的非递归实现是基于栈实现的。在递归中只有范围在不断改变，所以我们只需要在栈里存放范围即可。

要先在栈里存入序列的最左边的下标和最右边的下标。在排序时拿出下标。排完后再向栈中压入由它分出来的两个序列的左右下标。

//快速排序
void QuickSort(int* arr, int left, int right)
{
	ST 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 = begin;
		int prev = begin, cur = prev + 1;
		while (cur <= right)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);

		if (prev + 1 < end)//当只有一个数据时没必要入栈了
		{
			STPush(&st, end);
			STPush(&st, prev + 1);
		}
		if (begin < prev - 1)
		{
			STPush(&st, prev - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);//销毁栈
}