快速排序

      在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。

      快速排序是对冒泡排序的一种本质改进。

      基本思想：分治法，通过一趟扫描后，使得排序序列的长度能大幅度地减少。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

     快速排序：不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)

#include<iostream>
#include<cstring>

using namespace std;

int const ic_limit = 100002;

void vInputData(int &iNum,int iArr[]);
void vQuickSort(int iArr[],int iLeft,int iRight);
void vPrintAns(int iNum,int iArr[]);

int main()
{
	int iNum;
	int iArr[ic_limit];

	memset(iArr,0,sizeof(iArr));
	vInputData(iNum,iArr);
	vQuickSort(iArr,1,iNum);
	vPrintAns(iNum,iArr);

	return 0;
}

void vInputData(int &iNum,int iArr[])
{
	cin >> iNum;
	for(int i=1; i<=iNum; i++)
	{
		cin >> iArr[i];
	}
}

void vQuickSort(int iArr[],int iLeft,int iRight)
{
	int iKeyValue;
	int iLow;
	int iHigh;

	//以iKeyValue为基准
	iKeyValue = iArr[iLeft];
	iLow = iLeft;
	iHigh = iRight;
	while(iLow < iHigh)
	{
		while((iLow < iHigh) && (iArr[iHigh] >= iKeyValue))
		{
			iHigh --;
		}
		if(iLow < iHigh)
		{
			iArr[iLow] = iArr[iHigh];
			iLow ++;
		}
		while((iLow < iHigh) && (iArr[iLow] <= iKeyValue))
		{
			iLow ++;
		}
		if(iLow < iHigh)
		{
			iArr[iHigh] = iArr[iLow];
			iHigh --;
		}
	}
	iArr[iLow] = iKeyValue;

	if(iLeft < (iLow-1))
	{
		//对左区间递归排序
		vQuickSort(iArr,iLeft,iLow-1);
	}
	if((iLow+1) < iRight)
	{
		//对右区间递归排序
		vQuickSort(iArr,iLow+1,iRight);
	}
}

void vPrintAns(int iNum,int iArr[])
{
	for(int i=1; i<iNum; i++)
	{
		cout << iArr[i]  << " ";
	}
	cout << iArr[iNum] << endl;
}