首页 > 代码库 > 交换排序:快速排序

交换排序:快速排序

快速排序(Quick Sort)也是一种交换排序,它在排序中采取了分治策略。

快速排序的主要思想

  1. 从待排序列中选取一元素作为轴值(也叫主元)。
  2. 将序列中的剩余元素以该轴值为基准,分为左右两部分。左部分元素不大于轴值,右部分元素不小于轴值。轴值最终位于两部分的分割处。
  3. 对左右两部分重复进行这样的分割,直至无可分割。
从快速排序的算法思想可以看出,这是一递归的过程。

两个问题:

要想彻底弄懂快速排序,得解决两个问题:
  1. 如何选择轴值?(轴值不同,对排序有影响吗?)
  2. 如何分割?
问题一:轴值的选取?
轴值的重要性在于:经过分割应使序列尽量分为长度相等的两个部分,这样分治法才会起作用。若是轴值正好为序列的最值,分割后,元素统统跑到一边儿去了,分治法就无效了。算法效率无法提高。-看别人写快排的时候,注意他轴值的选取哦。

问题二:如何分割?
这涉及到具体的技巧和策略。在稍后的代码中我们一一介绍。

快速排序版本一

直接选取第一个元素或最后一个元素为轴值。这也是国内众多教材中的写法。
举个例子:
原序列   4   8   12   1   9   6
下标     0   1   2    3   4   5  轴值 pivot=4
初始化   i                    j
         i            j           i不动,移动j,while(i<j && a[j]>=pivot)j--; 
移动元素 1   8   12   1   9   6
             i        j           j不动,移动i,while(i<j && a[i]<=pivot)i++;
移动元素 1   8   12   8   9   6
            i,j                   再次移动j,i和j相遇,结束
最后一步 1   4   12   8   9   6   pivot归位
轴值4的左右两部分接着分割……

我想你一定看懂了,并且这轴值4,真的没选好,因为分割后左部分只有一个元素。

有人称上面的做法是:挖坑填数。这种描述真的很形象。简单解释下:首先取首元素为轴值,用变量pivot存储轴值,这就是挖了一个坑。此时,a[0]就是一个坑。接着移动j,把合适位置的j填入a[0],于是a[j]成了新的坑。旧的坑被填上,新的坑就出现。直到i和j相遇,这最后一个坑,被pivot填上。至此完成了第一趟分割……
看懂了,就动手敲代码吧!
void QuickSort(int a[], int n)  //快速排序,版本一
{
	if (a && n > 1)
	{
		int i, j, pivot;  //pivot轴值
		i=0, j = n - 1;
		pivot = a[0];   //第一个元素为轴值
		while (i < j)
		{
			while (i < j && a[j] >= pivot)
			j--;
			if (i < j)
			a[i++]=a[j];
			while (i < j && a[i] <= pivot)
			i++;
			if (i < j)
			a[j--]=a[i];
		}
		a[i] = pivot;   //把轴值放到分割处
		QuickSort(a, i);
		QuickSort(a + i + 1, n - i -1);
	}
} 

现在想想以最后一个元素为轴值的代码了,先别急着看,先动动手哦!代码如下:
void QuickSort(int a[], int n)
{
	if (a && n > 1)
	{
		int i, j, pivot;  //pivot轴值
		i = 0, j = n - 1;
		pivot = a[j];   //最后一个元素为轴值
		while (i < j)
		{
			while (i < j && a[i] <= pivot)
				i++;
			if (i < j)
				a[j--] = a[i];
			while (i < j && a[j] >= pivot)
				j--;
			if (i < j)
				a[i++] = a[j];
		}
		a[i] = pivot;   //把轴值放到分割处
		QuickSort(a, i);
		QuickSort(a + i + 1, n - i - 1);
	}
}

轴值选取策略

为了让轴值pivot不至于无效(不让pivot出现最值的情况)。我们可以使用一些策略来改进pivot的选取。

策略一:

随机选取序列中一元素为轴值。

int SelectPivot(int a[], int low, int high)
{
	int size = high - low + 1;
	return a[low + rand()%size];
}
选取首尾元素不就是该策略的一种特例!

策略二:

随机选取三数,取中位数。
int SelectPivot(int a[], int low, int high)
{
	int size = high - low + 1;
	int p1, p2, p3;
	p1 = low + rand()%size;
	p2 = low + rand()%size;
	p3 = low + rand()%size;
	if ( a[p1] <= a[p2])
	{
		if (a[p1] >= a[p3])   a[p3]=<a[p1]<=a[p2]
			return a[p1];
		else
		{
			if (a[p2] <= a[p3])
			return a[p2];
			else
			return a[p3];
		}
	}
	else
	{
		if (a[p1] <= a[p3])
			return a[p1];
		else
		{
			if (a[p2] <= a[p3])
			return a[p2];
			else
			return a[p3];
		}
	}
}
它的一种特例就是,选取原序列首、尾、中间三数,取它们的中位数。

目前看来基本常用的就这两种策略。不过我得吐槽一句:如果原序列中的元素本身就是随机存放的,也就是说,各个元素出现在各个位置的概率一样。那么特别地选取首位元素和随机选取又有什么区别呢?不知大家怎么看?
还得补充一句:随机选取轴值后,记得要把它和首或尾的元素交换哦。至于为什么?你懂的!

快速排序版本二

这也是《算法导论》上的版本。它的普遍做法是选取尾元素为pivot。重点是使用了一个分割函数:partition()。
伪代码与如下:
PARTITION(A, low, high)
1. pivot <- A[high]    //选取尾元素为轴值
2. i <- low-1          //把low-1赋值给i,下同
3. for j <- low to high-1    //j的变化范围[low, high-1]
4.      do if A[j] <= pivot
5.            then i <- i+1
6.            exchange A[i]<->A[j]
7. exchange A[i+1} <-> A[high]
8. return i+1;    //返回的是分割的位置
然后,对整个数组进行递归排序:
QUICKSORT(A, low, high)
1  if low < high
2  then q <- PARTITION(A, low, high)  //对元素进行分割就在这里
3  QUICKSORT(A, low, q - 1)
4  QUICKSORT(A, q + 1, high)

如果你不习惯于看伪代码,我来举个例子:(还是上面的序列)
原序列   4   8   12   1   9   6
下标  -1 0   1   2    3   4   5   轴值pivot是6
初始化 i j                        a[j]=a[0]=4<6,下一步先 i++;再swap(a[i],a[j]);随后j++;
交换     4   8   12   1   9   6
         i   j                    接着移动j
         i            j           a[j]=a[3]=1<6,下一步…
交换     4   1   12   8   9   6
             i            j       
             i                j   
交换     4   1   6    8   9   12  最后一步 swap(a[i+1], a[high]);或者是 swap(a[i+1], a[j]);
所以最后返回的是 i+1
用大白话讲讲上面的排序过程:用两个指针i,j,它们初始化为i=-1;j=0,接着让j不断地自增,遇到a[j]>pivot就与i交换,直到j指向末尾。
更直白的话:从头开始遍历原序列,遇到小于轴值的就交换到序列前面。

看懂了,就写代码了…
int partition(int a[], int low, int high)
{
	int i, j;
	i = low - 1;
	j = low;
	while (j < high)
	{
		if (a[j] < a[high])
		swap(a[++i], a[j]);
		j++;
	}
	swap(a[++i], a[high]);    //主元归位 
	return i;  //上面一步已经 ++i,所以这里不用 i+1 
}
void quicksort(int a[], int low, int high)
{
	if (low < high)  //至少两个元素,才进行排序 
	{
		int i = partition(a, low, high);
		quicksort(a, low, i - 1);
		quicksort(a, i + 1, high);
	}
}
void QuickSort(int a[], int n)
{
	if (a && n>1)
		quicksort(a, 0, n - 1);	
}

题外话:看到有的Api设计是这样的:QuickSort(int a[], int low, int high)。居然让用户多写一个0!如此不为用户考虑。应越简洁越好。排序只给数组名和数组大小,即可。
对上面的流程再思考:看到初始化i=-1;你不觉得奇怪吗?为什么i一定要从-1开始,仔细了解了i的作用,你会发现i本可以从0开始。这种做法的partition()方法是这样的:
int partition(int a[], int low, int high)
{
	int i, j;
	i = low;  //这里与上一种的做法不同哦!
	j = low;
	while(j < high)
	{
		if (a[j] < a[high])
		swap(a[i++], a[j]);
		j++;
	}
	swap(a[i], a[high]);    //主元归位 
	return i;
}

再思考:为什么j不能指向high?若是更改if(a[j]<a[high])为if(a[j]<=a[high),最后直接把a[high]交换到前面了,也就是说在while循环里面就完成了最后“主元归位”这一步。大家想想是不是?
此时的partition()是这样的:
int partition(int a[], int low, int high)
{
	int i, j;
	i = low;
	j = low;
	while (j <= high)
	{
		if (a[j] <= a[high])
		swap(a[i++], a[j]);
		j++;
	}
	return i;
}

至于有时候把quicksort()和partition()写成一个函数,那是再简单不过的事情,你肯定会的。

快速排序版本三:

上面用的都是递归的方法,把递归转化非递归总是不简单的,也总让人兴奋。这个版本就是快速排序的非递归写法;
void QuickSort(int a[], int low, int high)
{
	if (low < high)
	{
		stack<int> s;   //使用STL中的栈 
		int l,mid,h;
		mid = partition(a, low, high);
		/*
		首先存储第一次分割后的 [low, mid-1]和 [mid+1, high] 
		注意:这是成对存储的,取的时候注意顺序 
		*/ 
		if (low < mid-1)
		{
			s.push(low);
			s.push(mid - 1);
		}
		if (mid + 1 < high)
		{
			s.push(mid + 1);
			s.push(high);
		}
		//只要栈不为空,说明仍有可分割的部分 
		while(!s.empty())
		{
			h=s.top();
			s.pop();
			l=s.top();
			s.pop();
			mid = partition(a, l, h);
			if (l < mid - 1)
			{
				s.push(l);
				s.push(mid - 1);
			}
			if (mid + 1 < h)
			{
				s.push(mid + 1);
				s.push(h);
			}	
		}
	}
}

这个非递归的写法是很有意思的,很需要技巧。仔细想想,你能明白的。
提示:用栈保存每一个待排序子序列的首尾元素下标,下一次while循环时取出这个范围,对这段子序列进行partition操作。

小结:

快速排序号称快速搞定,时间复杂度是O(nlogn)。基本上是最优的排序方法。它的写法不外乎以上三种,大同小异。看到这里。你一定彻底了解了它。以上写法,都经过了本人测试,不知道你的测试是否和我一样?

转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/25436609

若是有所帮助,顶一个哦!

专栏目录看这里:数据结构与算法目录