KingsamChen的废墟堆

  RT，这两天写的，和上次那个三种常见排序遥相呼应~

  快速排序法（Quick Sort）可以看做一种改进的冒泡排序法，由C. A. R. Hoare提出并发展而来。对于排序n个元素，QS的时间复杂度的期望值是[tex]O\left(nlog_{2}^{n} \right)[/tex],而且QS在实际中，一般比其他[tex]O\left(nlog_{2}^{n} \right)[/tex]的的算法还要快。虽然QS在排序一些比较有序或完全有序的元素时，会退化成冒泡排序，时间复杂度跃升至 [tex]O\left(n^{2} \right)[/tex]，但是这种情况是极少出现的。（要知道，在某些情况下，Insertion Sort的时间复杂度可以达到[tex]O\left(n \right)[/tex]！）

  QS采用分治法（Divide and conquer）的策略逐一的把一个序列划分成两个子序列。其步骤可以概括为：
  1.从序列中挑出一个元素，成为“基准”（Pivot），设下标为p。
  2.遍历序列，使得小于p的元素放到一边，大于p的放到另一边（相等的可以放置到任意一边），将这个序列化分成两个子序列，这个操作成为“分割 ”（Partition）。即将数组A[L..H]分割成A[L...p-1]和A[p+1...H]，使得A[L..H]任意元素都小于等于A[p]，且小于等于A[p+1...H]。
  3.递归此操作，将小于基准值的子序列和大于基准值的子序列排序。

  这里，我们对于上面的步骤进行一些更深入的分析,并且用伪代码进行描述：

  1.对于如何挑选基准，一个理想的模型是，使得大于或小于基准两边的元素个数相近或相同，即使得序列保持平衡。通常的方法是在两个端点取值，但是某人（很显然，不是我≡ω≡）的统计概率分析标明，这样做经常会取到“很烂”的值，尤其是在排序那些比较有序的序列时，这样会使得两边的元素个数很不平衡（最糟糕的情况是每一次划分，某边的子序列都只有一个元素），因此出现了随机数版的QS版本（Random-Quick Sort）。

  其思想是随机从序列中取得基准或者随机从序列中取得三个数值，取其中位数为基准。

  不过这里，我想到了一个比较折中的方法，我们直接取原序列的中位数所对应的元素值作为基准。不过为了方便后面的排序，我们仍然必须把这个基准弄到序列的一端去。

  Q：为什么不直接分割，而要把基准弄到一边去？
  A：厄，还是那句话：现实中，基准两边完全平衡的概率是很低很低的！也就是说，虽然你现在是在正中间的位置，但是排序完之后，你还是得往两边挪，你那么硕大的体型挤在中间，别人过去不方便啊，非要别人带着你走来走去吗？你还是自觉的哪凉快哪呆着比较好！

  相应的伪代码如下：

‘To get a pivot
Mid <- (nLow + nHigh) / 2
Pivot <- A[Mid]
exchange A[nLow]<->A[Mid]

  2.基准选择完毕之后，我们需要对数据进行一次遍历（这里我更喜欢说扫描~），把他们分成两个子序列。

  扫描的方法也有不同的几种：Hoare最初给出的是从两边往中间扫描。如何扫描呢？我们先假想一个序列，并且有一个L游标对着左边第二个元素，一个R游标对着右边第一个元素。然后L游标往左边扫，扫啊扫，嘎~碰到一个元素，发现比基准大，于是L游标做稍息状休息。这个时候，R游标从右边往左扫，扫啊扫，叽~碰到一个元素，发现比基准小，又看看L游标，发现还在前面，于是两个人使出乾坤大挪移，把两个数据交换。

  接着L、R游标一边喊着“找啊找啊找朋友”，一边各自扫描。扫到什么时候结束呢？当L>R，即L游标和R游标相向而过。朋友都跑到自己后面去了，不停行么？

   就这样，完成一次扫描。这个时候，R游标所在的位置，就是基准应该呆的位置。以这个位置为界，划江而治。

   相应的伪代码如下：

‘scanning the list to divide it into two parts

L <- nLow + 1
R <- High

do repeat it
do while L < R and A[L] <= Pivot
L <- L + 1
end do

do while A[R] > Pivot
R <- R - 1
end do

if L < R then
exchange A[L] <-> A[R]
end if

until L > R

A[nLow] <- A[R]
A[R] <- Pivot

return R

  这里要注意一个问题，对于这种写法来说，两个do while中，必须要有一个要对相等情况作出处理，即必须有一个存在等号，而且对于上面的代码，等号必须是第一个do while中。

   这里，我们简要分析下。

   (1)L游标的移动受到两个因素的限制：L和R的位置关系以及L所指元素和基准的大小关系。这意味着，L游标一定会在序列内停止。

   (2)而R游标的移动只受到所指元素和基准大小这个一个因素的限制。我们上面的那段循环之所以能成立，是因为存在这么一个既定的推理：既然L停止移动，那么在R游标的左边一定存在一个元素，满足R游标的停止条件。

   (3)整个游标移动循环（就是那个大do….while）的停止条件是L > R,那么，前面的条件必须能够使得两个游标发生移动，并且能够交错

   由(2)可知，如果R游标的do while中包含=，那么R游标在某些条件下，比如一个等元素数组，就会移动出界。

   由(1)(2)(3)可知，如果L和R游标的do while均不包含=，那么就会导致游标无法移动，这部分代码陷入死循环。

   如果你真的想两个do while都包含=，那就修改R的停止条件。

   由于这种方式容易发生问题，所以出现了指定或直接控制循环次数的扫描版本以及算法导论中使用的单边扫描。单边扫描是从保存基准的另外一端开始扫描，仅用一个R游标，L游标仅作为两部分的分界线。

   由于条件限制，我只给出单边扫描的伪代码。

‘ one possible version

nPivot <- a[nHigh]
L <- nLow - 1
R <- nLow

for R <- nLow to nHigh - 1

if a[R] <= nPivot
L <- L + 1
exchange a[R]<->a[L]
end if

end for

return L + 1

  最后要说明一下，正常的QS应该是原地排序的，也就是说，不适用任何额外存储空间。虽然存在非原地排序的版本（WIKI上有伪代码），但是不推荐使用。

   3：前面两步完成之后，这步就显得很简单了~

int nPivIndex <- Partition1(a, nLow, nHigh)
QuickSort(a, nLow, nPivIndex - 1)
QuickSort(a, nPivIndex + 1, nHigh)

  本来想示范分析一下QS的时间复杂度的，但是由于这个有点复杂，偶只会分析最坏的情况-。-，所以就不献丑了~有兴趣可以看http://zh.wikipedia.org/zh-cn/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95

  最后，我们上代码~

/*
	输  入: a(int[]) - 要排序的数组
					nLow(int) - 第一个下标
					nHigh(int) - 最后一个下标
	输  出: -
	功  能: 快速排序法
*/
void CSort::QuickSort(int a[], int nLow, int nHigh)
{
	if (nLow >= nHigh)
	{
		return;
	}
	else if (nLow + 1 == nHigh)
	{
		// 若只有两个元素,直接比较

		if (a[nLow] > a[nHigh])
		{
			Swap(a[nLow], a[nHigh]);
		}

		return;
	}

	int nPivIndex = Partition2(a, nLow, nHigh);
	QuickSort(a, nLow, nPivIndex - 1);  // left
	QuickSort(a, nPivIndex + 1, nHigh);  // right
}

/*
	输  入: a(int[]) - 要排序的数组
					nLow(int) - 第一个下标
					nHigh(int) - 最后一个下标
	输  出: int - 基准所在下标位置
	功  能: 分离数组并就地排序
*/
int CSort::Partition(int a[], int nLow, int nHigh)
{
	// 取中位数所在元素作为基准
	int nMid = (nLow + nHigh) >> 1 ;
	int nPivot = a[nMid];
	// 交换,便于下面的排序
	Swap(a[nLow], a[nMid]);

	// you could also use the followed code instead
	//int nPivot = a[nLow];

	// 定义两个游标位置
	int nLeft = nLow + 1;
	int nRight = nHigh;

	do
	{
		// 左游标右移
		while ((nLeft < nRight) && (a[nLeft] <= nPivot))
		{
			nLeft++;
		}

		// 右游标左移
		// 注意:不要写>=,除非加上nLeft <= nRight
		// 否则会导致游标移出
		while (a[nRight] >= nPivot)
		{
			nRight--;
		}

		// 如果不是由于游标而停止
		if (nLeft < nRight)
		{
			Swap(a[nLeft], a[nRight]);
		}

	} while (nLeft < nRight);

	a[nLow] = a[nRight];
	a[nRight] = nPivot;

	return nRight;
}

int CSort::Partition2(int a[], int nLow, int nHigh)
{
	int nPivot = a[nHigh];
	int l = nLow - 1;
	int r = nLow;

	for (; r <= nHigh - 1; r++)
	{
		if (a[r] <= nPivot)
		{
			l++;
			Swap(a[r], a[l]);
		}
	}

	Swap(a[l+1], a[nHigh]);

	return l+1;
}