快速排序（QuickSort)

作者: admin 分类: 算法发布时间: 2013-02-16 13:28 ė6,940 浏览数 6没有评论

快速排序(QuickSort)也是一种排序算法，对包含n个数组的输入数组，最坏情况运行时间为O(n^2)。虽然这个最坏情况运行时间比较差，但是快速排序通常是用于排序的最佳实用选择，这是因为其平均性能相当好，期望的运行时间为O(nlgn)，且O(nlgn)中隐含的常数因子很小，另外它还能够进行就地排序在虚拟环境中也能很好的工作。

一、快速排序原理

快速排序也和合并排序一样，基于分治法，分为分解、解决、合并三个步骤；

分解：数组array[low...high]被分为两个(可能空)子数组array[low...temp-1]和array[temp+1...high]，使得array[low...temp-1]中的每一个元素都小于等于array[temp]，而array[temp+1...high]中的每一个元素都大于array[temp]，下标temp也是在这个过程中被计算出来；

解决：通过递归的调用快速排序，对子数组array[low...temp-1]，array[temp+1...high]进行排序；

合并：因为两个子数组是就地排序的，将他们的合并不需要操作，整个数组array[low...high]是已经排好序的。

二、快速排序实现

#include &lt;iostream&gt;
#include &lt;ctime&gt;
#include &lt;cstdlib&gt;
#define N 10

using namespace std;

//快速排序的递归算法
void quickSort(int * array , int low , int high);
//求分割点
int partition(int * array , int low , int high);
//交换两个变量的值
void exchange(int &amp;a,int &amp;b);

int main()
{
	//声明一个待排序数组   
    int array[N];  
    //设置随机化种子，避免每次产生相同的随机数    
    srand(time(0));   
    for(int i=0 ; i&lt;N ; i++)    
    {    
        array[i] = rand()%101;//数组赋值使用随机函数产生1-100之间的随机数      
    }    
    cout&lt;&lt;&quot;排序前：&quot;&lt;&lt;endl;    
    for(int j=0;j&lt;N;j++)    
    {    
        cout&lt;&lt;array[j]&lt;&lt;&quot;  &quot;;    
    }   
    cout&lt;&lt;endl&lt;&lt;&quot;排序后：&quot;&lt;&lt;endl;    
    //调用快速排序函数对该数组进行排序      
    quickSort(array,0,N-1);   
    for(int k=0;k&lt;N;k++)    
    {    
        cout&lt;&lt;array[k]&lt;&lt;&quot;  &quot;;    
    }    
    cout&lt;&lt;endl;    
    return 0;    
}//main

void quickSort(int * array , int low , int high)
{
	if(low &lt; high)
	{
		int temp = partition(array , low , high);
		quickSort(array , low , temp-1);
		quickSort(array , temp+1 , high);
	}
}

int partition(int * array , int low , int high)
{
	int i = low - 1;
	int x = array[high];

	for(int j=low ; j&lt;high ; j++)
	{
		if(array[j] &lt;= x)//在array[i]左边都是小于x即array[high]的数，右边均是大于它的数
		{
			i += 1;
			exchange(array[i],array[j]);
		}
	}
	exchange(array[i+1],array[high]);
	return i+1;//所以循环完毕后，i+1就是该数组的分割点
}
void exchange(int &amp;a,int &amp;b)
{
	int temp = a;
	a = b;
	b = temp;
}

#include <iostream>

#include <ctime>

#include <cstdlib>

#define N 10

using namespace std;

//快速排序的递归算法

void quickSort(int * array , int low , int high);

//求分割点

int partition(int * array , int low , int high);

//交换两个变量的值

void exchange(int &a,int &b);

int main()

{

//声明一个待排序数组

int array[N];

//设置随机化种子，避免每次产生相同的随机数

srand(time(0));

for(int i=0 ; i<N ; i++)

{

array[i] = rand()%101;//数组赋值使用随机函数产生1-100之间的随机数

}

cout<<"排序前："<<endl;

for(int j=0;j<N;j++)

{

cout<<array[j]<<" ";

}

cout<<endl<<"排序后："<<endl;

//调用快速排序函数对该数组进行排序

quickSort(array,0,N-1);

for(int k=0;k<N;k++)

{

cout<<array[k]<<" ";

}

cout<<endl;

return 0;

}//main

void quickSort(int * array , int low , int high)

{

if(low < high)

{

int temp = partition(array , low , high);

quickSort(array , low , temp-1);

quickSort(array , temp+1 , high);

}

int partition(int * array , int low , int high)

{

int i = low - 1;

int x = array[high];

for(int j=low ; j<high ; j++)

{

if(array[j] <= x)//在array[i]左边都是小于x即array[high]的数，右边均是大于它的数

{

i += 1;

exchange(array[i],array[j]);

}

exchange(array[i+1],array[high]);

return i+1;//所以循环完毕后，i+1就是该数组的分割点

}

void exchange(int &a,int &b)

{

int temp = a;

a = b;

b = temp;

}

三、快速排序性能分析

快速排序的运行时间与划分是否对称有关，而后者又与选择了哪一个元素进行划分有关。如果划分是对称的，那么本算法在渐近意义上与合并排序一样快，如果划分是不对称的那么本算法在渐进意义上与插入排序一样慢。下面分别讨论快速排序的最坏情况划分、最家情况划分、平衡的划分。

最坏情况划分：快速排序的最坏情况划分行为发生在划分过程中产生的两个区域分别包含n-1个元素和0个元素的时候。假设算法每次递归调用都出现了这种不对称划分，划分的时间代价为O(n)，因为对一个大小为0的数组进行递归调用后，返回了T(n)=O(1)，故算法的运行时间可递归的表示为：

T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)

从直观上来看，如果将每一层递归的代价加起来，就可以得到一个算术级数(等式(array,2)其和值的量极为O(n^2))利用代换法可以比较直接的证明递归式 T(n) = T(n-1) + O(n)的解为 T(n) = O(n^2)。

因此如果在算法的每一层递归上，划分都是最大程度不对称的，那么算法的运行时间为O(n^2)，亦即快速排序算法的最坏情况运行时间不如插入排序的好。此外当输入数组完全排好序时，快速排序的运行时间是O(n^2)，而插入排序的运行时间为O(n)。

最佳情况划分：在Partition可能做的最平衡划分中，得到的两个子问题的大小都不可能大于[n/2]，因为若其中一个子问题的大小为[n/2]，则另外一个子问题的大小必然为[n/2]-1。在这种情况下，快速排序的运行速度要快得多，这时表达其运行时间的递归式为：

T(n) <= 2T(n/2) + O(n)

解该递归式可得T(n) = O(nlgn)。由于在每一层递归划分的两边都是对称的，因此从渐进意义上来看，算法运行的就更快了。

平衡的划分：快速排序的平均情况运行时间与其最佳情况运行时间很接近，而不是非常接近与其最坏情况运行时间(证明原因详细参考《算法导论》原书第二版P88)，因为任何一种按常数比例进行划分都会产生深度为O(lgn)的递归树，其中每一层的代价都是O(n)，因而每当按照常数比例进行划分时，总的运行时间都是O(nlgn)。