快速排序几乎是最快的排序算法。在所有关键字为逆序时排序速度最快。

基本思想：在待排记录中选取一个记录做为枢纽。数组中的数据与枢纽作对比，从而分成两部分，左边小于枢纽值，右边部分大于枢纽值。枢纽为分界线。

划分过程如下：

（1）选取数组第一个数字作为基准，存储起来，设两个值分别指向数组头部尾部的下标，分别为i,j。

（2）a[j]与基准作比较，若a[j]大于基准，则j前移，直到找到第一个小于基准的值，此时，若i<j,则a[i]=a[j];

（3）a[i]与基准作比较，若a[i]小于基准，则i前移，直到找到第一个大于基准的值，此时，若i<j，则a[j]=a[i];

(4)重复（2）（3），直到i==j。

平均情况的时间复杂度          最好情况的时间复杂度               最坏情况的时间复杂度               空间复杂度

        O(nlog2(n))                         O(nlog2(n))                               O(n^2)                         O(log2(n))~O(n)

#include<iostream>
using namespace std;
template<class Type>
int Partition(Type a[],int i,int j)
{
	Type tem=a[i];
	while(i<j)
	{
		while(i<j&&a[j]>=tem)
		j--;
		if(i<j)
		a[i++]=a[j];
		while(i<j&&a[i]<=tem)
		i++;
		if(i<j)
		a[j--]=a[i];
   }
   a[i]=tem;
   return i;
}

template<typename Type>
void QuickSort(Type a[],int i,int j)
{
	int pivot;
	if(i<j)
	{
		pivot=Partition(a,i,j);
		QuickSort(a,i,pivot-1);
		QuickSort(a,pivot+1,j);
	}
}
int main()
{
	int a[7]={49,27,65,97,76,13,38};
	for(int i=0;i<7;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	QuickSort(a,0,6);
	for(int i=0;i<7;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}