参考了《数据结构域算法分析》书上部分代码，结合自己的理解写出的快速排序程序。书上用三数中值分割法来选择枢纽元，有它的好处，但我觉得使得代码很多地方不够直观。我选择数组的最后一个元素作为枢纽元，然后实现了快排。

关于快排的原理可以去看我博客转载的文章，很直观：点击打开链接

快排的步骤就是：

1.选择枢纽元  

2.将小于枢纽元的数放前面，大于枢纽元的数放后面，枢纽元放中间 

                3.然后对枢纽元左右两个部分继续进行1和2  

下面程序中最主要的是Quicksort，实现了快排的原理，而子函数Qsort只是为了简洁的调用Quciksort而写的。Quicksort中有很多输出语句，只是为了把快排的每一个递归都显示出来，可以无视。

#include <iostream>
using namespace std;

void swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void Quicksort(int a[], int Left, int Right)
{
	int i ,j;
	int Pivot = a[Right];   //选取数组最右的值为枢纽元
	if( Left < Right )      //读入a[]至少有两个数据才能进入后续步骤
	{
		i = Left;
		j = Right-1;        //由于最右为枢纽元，所以实际操作中的数组最右是Right-1
		for( ; ; )
		{
			while( a[i] < Pivot && i<Right ) {i++;}     // i<Right 防止越上界
			while( a[j] > Pivot && j>0 ) {j--;}         // j > 0   防止越下界
			if( i < j )
			{
				swap( &a[i], &a[j] );
				i++;
				j--;
			
				for(int i=0;i<10;i++)
				{
					cout<<a[i]<<' ';
				}
				cout<<endl;
			}
			else
				break;
		}
		swap(&a[i], &a[Right]);

		for(int i=0;i<10;i++)
		{
			cout<<a[i]<<' ';
		}
		cout<<endl;

		Quicksort(a, Left, i-1);
		Quicksort(a, i+1, Right);
	}

}

void Qsort(int a[], int N)
{
	Quicksort( a, 0, N-1 );
}

void main()
{
	int a[10] = { 10, 6, 4, 8, 3, 9, 1, 5, 2, 7};
	int N = 10;

	cout<<"初始数组为："<<endl;
	for (int i=0; i<10; i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;

	cout<<"快排步骤及结果："<<endl;
	Qsort( a, N );
}