学步园

快速排序采用的思想是分治思想。

快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

#include <iostream>
#define LEN 20
using namespace std;

	void inline swap(int &a,int &b)
	{
		if(a==b)
		{
			return ;
		}
		a=a^b ;
		b=a^b ;
		a=a^b ;
	}


	int Partition(int a[],int left,int right)
	{
		int pivot=right ;//默认最右边值为基准值
		int i=left ;
		int j=left ;
		for(j=left;j<right;j++)
		{
			if(a[j]<a[pivot])   //如果符号改为大于， 即实现了从大到小排列
			{
				swap(a[j],a[i++]) ;//理解这一步是关键 i为基准点，即i左边 （0——i-1）都为小于基准点的数字		}
			}
		}
			swap(a[i],a[pivot]) ;    //将本次分割的基准值放入a[i]处
			return i ;
	}


		void QuikSort(int n[],int left,int right)
		{
			int tmp ;
			if(left<right)
			{
				tmp=Partition(n,left,right) ;
				QuikSort(n,left,tmp-1) ;
				QuikSort(n,tmp+1,right) ; 
			}
		}

		int main(int argc,char **argv)
		{
			int n[]={ 12, 24, 12, 4, 9, 11, 34, 53,5,4,3,7,1,10,9,8,5,6,5,4};
			for(int m=0;m<LEN;m++)//排序前
				cout<<n[m]<<"," ;
			cout<<endl;
			QuikSort(n,0,19) ;
			for(int m=0;m<LEN;m++)//排序后
				cout<<n[m]<<"," ;
			cout<<endl;

			return 0 ;
		}