快速排序算法分析及其改进

基本算法

快排也是一种分治算法，所谓分治，也就是将大问题不断切分成小问题进而着眼于小问题的解决

我们在讨论归并排序的时候，我们是从小数组着手。我们不断地将小数组排序，再对有序的两个小数组组合成一个大的有序的数组。这种思想可以说是从分治的角度去考虑问题时一个最容易想到的（快排这个还真不一定那么容易想到，至少我是这么认为的）

快排的思想是，不断地对数组进行切分，切分得到的两个部分当中的数，有：

• 左边的数全部小于切分点
• 右边的数全部大于切分点

我们得到两部分后，再重复执行上述操作，就可以最终实现快排

class Qsort
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	void sort(vector<int>& a)
	{
		sort(a, 0, a.size() - 1);
	}

	void sort(vector<int>& a, int lo, int hi)
	{
		if (lo >= hi)//区间最少需要两个数
			return;
		int mid = partition(a, lo, hi);
		sort(a, lo, mid - 1);
		sort(a, mid + 1, hi);
	}
};

partition 方法会选择数组当中某个数作为切分点，然后将所有小于这个数的全部放到左边，大于这个数的全部放到右边，最后返回切分点的下标

现在，我们需要去实现 partition

我们通常会选择数组第一个元素 a[lo] 作为切分元素 v，然后从左往右扫描，找到第一个大于 a[lo] 的数，再从右往左扫描，找到第一个小于 a[lo] 的数。显然，这两个数是没有进行排序的，我们将交换这两个元素，之后再不断重复这个过程

在结束循环的时候，会有两种情况，我们重点讨论一下：

• 当 i == j 时， i 左边的元素全部小于 v ，j 右边的元素全部大于 v 因此当二者相遇时，只有可能是 a[i] == a[j] == v 。由于 v 的初始位置是在 i 的左边，也就是说这个位置的值需要小于 v （等于也没关系），因此我们将一个等于 v 的值放在第一个位置，这是没问题的
• 当 j <= i 时，同样的道理，i 左边的元素小于 v ，j 右边的元素大于 v 。而当 j 在 i 左边， i 在 j 右边时，j 的值一定小于 v ，i 的值一定大于 v ，而第一个位置的值只能是小于 v ，因此只能将 j 的值与 v 进行交换

完整代码如下：

class Qsort
{
public:
	static bool less(int v, int w)
	{
		return v < w;
	}

	static void exch(vector<int>& a, int i, int j)
	{
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	void sort(vector<int>& a)
	{
		sort(a, 0, a.size() - 1);
	}

	void sort(vector<int>& a, int lo, int hi)
	{
		if (lo >= hi)//区间最少需要两个数
			return;
		int mid = partition(a, lo, hi);
		sort(a, lo, mid - 1);
		sort(a, mid + 1, hi);
	}

	int partition(vector<int>& a, int lo, int hi)//对[lo,hi]切分
	{
		int i = lo, j = hi + 1;
		int v = a[lo];
		while (true)
		{
			while (less(a[++i], v));
			while (less(v, a[--j]));
			if (i >= j)
				break;
			exch(a, i, j);
		}
		exch(a, lo, j);
		return j;
	}
};

​

算法分析

\[ 命题K: 将长度为N的无重复数组排序，快速排序平均需要\sim 2NlogN次比较 \]

令 \(C_N\) 为将 \(N\) 个不同元素排序平均所需的比较次数。显然 \(C_0=C_1=0\) ，当 \(N>1\) 时，有： \[ C_N=(N+1)+\frac{(C_0+C_1+C_2+\cdots+C_{N-1})}{N}+\frac{(C_{N-1}+C_{N-2}+\cdots+C_1+C_0)}{N} \] 第一项表示切分成本（\(N\) 个数，切分点的选择有 \(N-1\) 种可能），第二项为将左子数组排序所需的平均成本（左子数组的长度为 \(0\) 到 \(N-1\) ），第三项为将右子数组排序所需的平均成本（右子数组的长度也为 \(0\) 到 \(N-1\)）

将等式左右两边乘以 \(N\) ，有： \[ NC_N=N(N+1)+2(C_0+C_1+C_2+\cdots+C_{N-1}) \] 减去当 \(N=N-1\) 时的等式时，有： \[ NC_N-(N-1)C_{N-1}=2N+2C_{N-1} \] 同时除以 \(N(N+1)\) ，有： \[ \frac{C_N}{(N+1)}=\frac{C_{N-1}}{N}\cdot2(N+1) \] 迭代后，有： \[ C_N\sim 2(N+1)(\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{N+1}) \] 括号内的量是曲线 \(2/x\) 下从 \(3\) 到 \(N\) 的离散近似面积加一，积分得到 \(C_N \sim 2N\ln N\) 。注意到 \(2N\ln N \sim 1.39N\lg N\) ，也就是说，平均比较次数只比最好的情况多 \(39\%\) \[ 命题L: 快速排序最多需要约N^2/2次比较 \] 假设我们切分的时候，总有一个子数组为空，那么上式为： \[ C_N=C_{N-1}+1 \] 即： \[ N+(N-1)+(N-2)+\cdots + 1 \sim N(N+1)/2 \] ​

算法改进

切换到插入排序

我们看到，对于小数组而言，快排的速度其实不见得很快

对于这种只有几个数的小数组，我们可以用插入排序来进行解决

快排的返回语句为：

if(lo >= hi) return;

我们可以改为：

if(lo + M >= hi) 
{
    Intersection.sort(a, lo, hi);
    return;
}

其中 M 的取值可以为 5 到 15 ，然后我们需要手动实现一个给定区间的插入排序，不过这个并不困难

​

三取样切分