Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » ,

快速排序的实现与应用

快速排序(Quick Sort)是一种非常经典高效的排序算法,采用了基于比较的递归分治策略,平均情况下复杂度为O(nlogn),但最坏情况会退化到O(n^2)。
在笔试面试过程中经常会有关于快速排序的问题,甚至要求面试者当场手写代码,本文将简单介绍快排原理并提供具体的代码实现,以及其在求第n小的数中的经典应用。

一 系统函数

C++的STL已经提供了快速排序的函数sort,在实际场合如比赛的过程中可以直接进行调用。

使用快速排序函数需要使用#include <algorithm>包含头文件,使用时把数组的头尾指针传递进去即可。注意尾指针的元素并不参与排序

sort默认完成的是从小到大的排序,需要其他规则的排序时可以自定义排序的比较函数,使用比较函数可以对任意的自定义类型进行排序。

具体的使用方法如下所示:

bool cmp(const int &a, const int &b){ return a > b; } //比较函数

void test1()
{
	int x[] = {4, 3, 1, 2, 5}, n = 5;
	cout << "原始:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//原始:4 3 1 2 5

	sort(x, x+n);		//从小到大
	cout << "升序:";
	for (int i = 0; i < n; i++) cout << x[i] << " "; 
	cout << endl;			//升序:1 2 3 4 5

	sort(x, x+n, cmp);		//根据cmp规则排序,这里是从大到小
	cout << "降序:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//降序:5 4 3 2 1
}

二 C++实现

快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序。

算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大。划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法。

选择最右边的数字作为基数。使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值。然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]属于左边的数,就把j自增,然后交换a[j]和当前的a[i]。因为自增前的j是左边数字最右的下标,自增后的a[j]肯定不属于左边了,把其跟a[i]交换后,新的a[j]是属于左边的,而且此时j也重新变为左边数字最右的下标了。

扫描结束后,把j自增(因为a[j]将会被交换到最右边,因此要选属于右边的数字)后与最右边的基数交换,此时的j即为划分的结果。

实际应用中有一个优化,因为快速排序在数组本来有序的情况下复杂度会退化为O(n^2)。为了避免这点,在选取基数的时候可以随机地进行选择。具体做法是把最右边的数字跟一个随机的数字交换位置。另外还有一种三数取中的方法,即选择首尾跟中间某个数共三个数的中值作为基数。

具体代码实现为:

int partition(int a[], int l, int r) //对数组a下标从l到r的元素进行划分
{
	//随机选取一个数作为划分的基数
	int rd = l + rand() % (r-l+1); 
	swap(a[rd], a[r]);

	int j = l - 1; //左边数字最右的下标
	for (int i = l; i < r; i++)
		if (a[i] <= a[r]) 
			swap(a[++j], a[i]);
	swap(a[++j], a[r]);
	return j;
}

划分完成之后快速排序就很简单了,代码如下:

void quickSort(int a[], int l, int r) //对数组a下标从l到r的元素排序
{
	if (l >= r) return;
	int m = partition(a, l, r);
	quickSort(a, l, m-1);
	quickSort(a, m+1, r);
}

这里也用一个简单的例子进行测试:

void test2()
{
	int x[] = {4, 3, 1, 2, 5}, n = 5;
	cout << "原始:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//原始:4 3 1 2 5

	quickSort(x, 0, n-1);
	cout << "升序:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//升序:1 2 3 4 5
}

刚刚提到,划分数组时有另一种双向扫描的方法。

还是以最右边的元素作为基数。目的是左边的元素都是小于或等于基数,右边的元素都是大于基数的。先不管最右的数字,i从左往右扫描知道遇到一个不属于左边的数字,j从右往左扫描直到遇到一个不属于右边的数字,然后就可以交换i和j上的数字,那么这两个数字就放在了它们应该在的位置。然后i++,j–再继续扫描,直到i和j相遇。最后要把最右边的基数和i上面的数字交换,i就是划分的结果。

代码如下:

int partition2(int a[], int l, int r)
{
	int i = l, j = r - 1;
	while (1)
	{
		while (i <= j && a[i] <= a[r]) i++; //左边元素<=基数
		while (i <= j && a[j]  > a[r]) j--; //右边元素 >基数
		if (i >= j) break;
		swap(a[i++], a[j--]); 
	}
	swap(a[i], a[r]); //i == j
	return i;
}

三 简单应用

快速排序有许多应用,其中一个是求一个数组中的第n个数。

求第n个数时可以把数组进行排序,然后直接取出第n个数。但这样做了许多不必要的排序,实际上可以进行部分排序,每次进行划分之后判断要求的第n个数时在左边还是右边,然后直接排序相应的部分即可。在部分排序左边或者右边的时候,需要把n换成在当前排序部分中的新的n值。

注意这样求得第n个数时数组元素的顺序已经被改变了。

int NthElement(int a[], int l, int r, int id) //求数组a下标l到r中的第id个数
{
    if (l == r) return a[l];        //只有一个数
    int m = partition(a, l, r), cur = m - l + 1;
    if (id == cur) return a[m];							//刚好是第id个数
    else if(id < cur) return NthElement(a, l, m-1, id); //第id个数在左边
    else return NthElement(a, m+1, r, id-cur);			//第id个数在右边
}

这里使用了上面的partition函数进行划分。一个简单的测试例子为:

void test3()
{
	int x[] = {4, 3, 1, 2, 5}, n = 5, id = 3;
	cout << "原始:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//原始:4 3 1 2 5

	cout << "第" << id << "个数:" << NthElement(x, 0, n-1, id);
	cout << endl;			//第3个数:3
}

使用这种方法可以直接求一个无序数组的中位数,对于带权中位数可以通过在计算id和cur的关系时先统计l到m的权值之和再分析得到。

另外,对于这个简单的应用STL也提供了相应的函数进行求解,实际中也不用自己实现。STL中的函数是algorithm头文件中的nth_element函数,使用nth_element(a, a + mid, a + n)会对数组a进行部分排序,结果保证第mid+1个数是正确的。

具体的使用方法如下:

void test4()
{
	int x[] = {4, 3, 1, 2, 5}, n = 5, id = 3;
	cout << "原始:";
	for (int i = 0; i < n; i++) cout << x[i] << " ";
	cout << endl;			//原始:4 3 1 2 5

	nth_element(x, x + id - 1, x + n);
	cout << "第" << id << "个数:" << x[id- 1];
	cout << endl;			//第3个数:3
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论