快速排序（分治策略）

算法划分图示

如图，以首元素27为基准，定义i和j，i向右遍历，j向左遍历。首先由j开始进行遍历，直到遇到小于27的元素时停下。此时i开始进行遍历，直到遇到大于27的元素时停下。此时交换i和j所指向的元素。然后j和i开始第二次的遍历… …直到最后i遍历遇到了j，令27与j所指向的元素16进行交换。至此第一次对数组的排序结束。

算法思想

1. 以首元素A[0]作为划分的标准，将这组元素划分成不超过A[0]的元素构成的数组AL,和大于A[0]的元素组成的数组AR。AL和AR分别位于A[0]的左右两边。
2. 递归的调用此算法，分别对AL和AR继续进行排序。

代码实现

#include<iostream>
#include<algorithm>

using namespace std;

void QuickSort(int *arr,int p,int r)    //p:数组首元素  r:数组尾元素 
{
	if(p<r)
	{
		int i=p,j=r+1;
	    int x=arr[p];    //首元素赋值给x 
	    while(true)
	    {
		    while(arr[++i]<x&&i<r);    //从第二个元素开始遍历，判断是否小于x 
		    while(arr[--j]>x);    //从最后一个元素开始遍历，判断是否大于x 
		    if(i>=j)    //跳出while循环 
		        break;
		    swap(arr[i],arr[j]);    //当i寻到大于x的元素，j寻到小于x的元素时，进行交换 
	    }
	    arr[p]=arr[j];
	    arr[j]=x;
	    QuickSort(arr,p,i-1);    //递归的对小于x的元素继续进行排序 
		QuickSort(arr,j+1,r);    //递归的对大于x的元素继续进行排序 
	}
}

int main()
{
	/*int n;
	cin>>n;
	int num[n];
	for(int i=0;i<n;i++)
	{
		cin>>num[i];
	}*/
	int num[12]={19,35,23,87,45,23,56,78,10,45,26,64};
	int n=12;
	QuickSort(num,0,n-1);    //以数组的第一个元素作为基准元素 
	cout<<"排序后的数组为："<<endl;
	for(int i=0;i<n;i++)
		cout<<num[i] << ' ';
	cout<<endl;
	return 0;
}
           

时间复杂度

最坏情况

最坏情况发生在划分之后所产生的左右两个区域的元素数量分别为n-1和1个的时候。因为QuickSort函数执行一次的时间复杂度为O(n)，所以假设每次递归的执行QuickSort函数时都会出现这种极端情况，则其时间复杂度满足：

W(n)=W(n-1)+n-1

W(1)=0

解的

W(n)=n(n-1)/2

其时间复杂度为O(n²）。

最好情况

最好情况发生在每次递归执行QuickSort函数后，其划分所产生的左右两个区域的元素数量均等，两边元素数量都为n/2，此时其时间复杂度满足：

W(n)=2W(n/2)+n-1

W(1)=0

解的

W(n)=θ(n log n)

其时间复杂度为O(n log n)。平均情况下的时间复杂度也为O(n log n)。