[Algorithm_Learn_04]分治法之快速排序

代码实现可到此处下载：http://download.csdn.net/detail/elcarim/6542567

当前代码工程中包含了 堆排序、快速排序，后面会持续更新。

在归并排序中我们已经讨论过一次分治法在排序算法中的应用，这篇文章中使用的快速排序法将会再次使用分治思想。

1快速排序有多快

与它的名字一样，快速排序有着很高的效率。如算法导论中所述，虽然其最坏情况的时间复杂度为ϑ(n^2)，但如下两点使其成为排序方法中最佳的选择：

1、平均性能好，期望时间复杂度为ϑ(nlgn)，结合随机化算法将待排序的数据顺序随机化，将会使其更容易达到期望性能。

2、较小的常数因子，使其比堆排序更有优势。

2 原理说明

如果找对切入口，快速排序的思想是非常容易理解的。与其他分治算法一样，其核心无外是对数据进行分割。归并排序是折半分割，快速排序想要有更快的速度，当然就需要更精细的分割方法。

下图是快速排序的一个简单流程（按升序排序的处理方法），主要包括如下几个步骤：

Ø Step 1选取参照点：固定选择数组的最后一个元素为参照点，记为refer，如图中蓝色元素。

Ø Step 2 分割集合：将剩余的元素逐个与参照点进行比较，按照大小划分为两个集合A和B。A = {x| x <= refer}, B = {x | x > refer }. 比较完后，将参照点放置到集合A和B的中间，有不等式 A <= refer < B 成立。注意，这里得到的集合A、B中的元素仍然是无序的，因此需要继续进行下面的步骤。

Ø Step 3 递归排序：分别对集合A、B中的元素进行排序，跳转到Step1。注意，上次使用的参考点被置为灰色，排除在集合A、B之外，不再参与排序。当A或B中的元素只剩一个时，递归结束。最终得到一个按升序排列的数组。

上图已经解释了快速排序的基本思想，但是有两个问题还需要深入讨论：

（1）如何实现原地排序？由于快速排序是递归调用，每次调用我们都会得到两个集合A、B。那么，在算法的实现过程中，如何保存这两个集合且不必申请额外的空间呢？

（2）每次选取最后一个元素作为参照点是否合理，会不会出现一种极端情况，即每次分割后集合A或B中只有一个元素，这样需要n次递归才能完成排序。即出现最坏情况，时间复杂度为ϑ(n^2)。解决这个问题需要用到随机化方法。

下面针对这两个问题进行讨论，这两点对算法的实现很重要！

3原地排序

为了实现原地快速排序，需要好好利用输入的数组空间。实际上，在排序过程中，需要将数组分为四个区间，如下图：

Ø less: 小于等于refer的集合。

Ø larger：大于refer的集合。

Ø remain：待比较的数。

Ø refer：参考数。

划分四个区间需要三个分割点，因此需要记录三个指针：

Ø Lager index：lager区间的起始位置。

Ø Remain index：remain区间的起始位置。

Ø Reference index：refer区间的起始位置。

按照上述划分方法，举一个例子，如下图：

Step 1: 选择参考点，初始化三个指针的位置。

Step 2：remain区间的第一个元素与refer比较，8 > 6，将8放在larger区间中，larger区间起始位置不变，remain区间起始位置后移一位。

Step 4: 2 < 6，需要将2放在less区间中，即放置到larger区间的前面。首先交换larger区间中第一个元素8和2的位置，然后将larger区间的起始位置后移一位即可。remain区间起始位置仍然后移一位。

Step 5: 经过若干次比较后，remain区间中元素为0，此时remain_index等于reference_index。

Step 6：最后，将refer放在区间less和larger之间。交换larger区间中第一个元素和refer的位置，然后将larger区间的起始位置后移一位即可。

4随机方法

通过随机选取参考数refer，使算法的期望时间复杂度趋近于ϑ(nlgn)。证明方法算法导论上已有详细介绍，这里不再赘述。

为了减小随机化方法对原算法实现的影响，每次从数组中随机选取一个参考点后，将该点与数组中的最后一个元素交换，后面的排序过程与原算法一样，非常简单！如下图：

从数组中随机选择，得到9做为参照数。将其与最后一个元素6交换位置，后面在进行排序时，仍然可以沿用原算法，使用最后一个元素作为参照数。

5代码实现

/*********************************************************************************/
/*Description: 快速排序法。
/*********************************************************************************/
class QuickSort{
protected:
	int * m_data;
	int m_op;     //排序方式

public:
	int Sort(int type, int head, int tail, int * data);

protected:
	void ExcuteSort(int head, int tail);
	virtual int Partition(int head, int tail);
};

/*********************************************************************************/
/*Description: 随机化快速排序法，从快速排序法继承而来。
/*********************************************************************************/
class RandQuickSort:public::QuickSort{
private:
	int Partition(int head, int tail);
};

/*********************************************************************************/
/*Description: 外部接口，进行快速排序。
/*********************************************************************************/
int QuickSort::Sort(int type, int head, int tail, int * data)
{
	if (!data || head > tail)
	{
		return FAILURE;
	}

	m_op   = type;
	m_data = data;
	ExcuteSort(head, tail);
}

/*********************************************************************************/
/*Description: 快速排序的递归调用。
/*********************************************************************************/
void QuickSort::ExcuteSort(int head, int tail)
{
	if (head < tail)
	{
		int mid = Partition(head, tail);
		ExcuteSort(head, mid - 1);
		ExcuteSort(mid + 1, tail);
	}
}

/*********************************************************************************/
/*Description: 快速排序，对数据进行分割。
/*********************************************************************************/
int QuickSort::Partition(int head, int tail)
{
	int refer = tail;
	int larger = head;
	int remain = head;

	while (remain < refer)
	{
		if (ST_ASC == m_op && m_data[remain] <= m_data[refer])
		{
			Swap(&m_data[larger], &m_data[remain]);
			++larger;
		}

		if (ST_DSC == m_op && m_data[remain] >= m_data[refer])
		{
			Swap(&m_data[larger], &m_data[remain]);
			++larger;
		}

		++remain;
	}

	int mid = larger;
	Swap(&m_data[larger], &m_data[refer]);

	return mid;
}

/*********************************************************************************/
/*Description: 重载父类的Partition方法，随机选取参照数，然后再进行数据分割。
/*********************************************************************************/
int RandQuickSort::Partition(int head, int tail)
{
	int random = head + rand() % (tail - head + 1);  //random [0, tail-head]
	Swap(&m_data[random], &m_data[tail]);
	return QuickSort::Partition(head, tail);
}