快速排序

有多种做法可以写出快速排序，但思路都是一样的，通过选定一个轴值，将数组分为两部分，比轴值小的排在轴值左侧，比轴值大的排在轴值右侧，然后分别对轴值两侧的部分再进行前述操作，直到整个数组有序。

法一：选定数组首位为轴值，分别顺序从右左两侧相向扫描，从右侧扫描时，左指向为轴值，右指向比轴值小则交换左右指向值；从左侧扫描时，右指向为轴值，左指向比轴值大或等于轴值时交换左右指向值，当左右指向相等的时候结束本轮排序，并分别将轴值左右两部分进行下一轮排序，直到整个数组有序。

法二：选定数组首位为轴值，对数组除首位外的剩余数组部分分别进行右左扫描，当右指向值比轴值小、左指向值比轴值大或等于轴值时，交换左右指向值，重复进行此过程直到左右指向相同，然后对轴值和右指向值进行比较，若轴值大于右指向值则交换双方，否则右指向左移一位，原因是当退出循环时，左右指向相同，但指向的值与轴值的大小关系尚未确定，若指向值比轴值大，则可以将指向值作为轴值（此时指向值左侧都比指向值小），否则必须要将指向值与轴值交换。接着将指向左右两侧的数组部分再次进行上述过程，直到整个数组有序。

#include<iostream>
using namespace std;

//法一
template<typename T>
void quickSort(T a[], int start, int end)
{
	if (start >= end)
		return;
	int left = start;
	int right = end;
	while (left < right)
	{
		while (a[right] >= a[left] && left < right)
		{
			right--;
		}
		if (left < right)
		{
			swap(a[left], a[right]);
			left++;
		}
		while (a[right] >= a[left] && left < right)
		{
			left++;
		}
		if (left < right)
		{
			swap(a[left], a[right]);
			right--;
		}
	}
	quickSort(a, start, left - 1);
	quickSort(a, left + 1, end);
}

//法二
template<typename T>
void quick_sort(T a[], int start, int end)
{
	if (start >= end)
		return;
	int left = start + 1;
	int right = end;
	T mid = a[start];
	while (left < right)
	{
		while (a[right] >= mid && left < right)
			right--;
		while (a[left] < mid && left < right)
			left++;
		swap(a[left], a[right]);
	}
	if (a[start] > a[right])
		swap(a[start], a[right]);
	else
		right--;
	quickSort(a, start, right - 1);
	quickSort(a, right + 1, end);
}

int main()
{
	while(true)
	{
		int n;
		cin>>n;
		int* a=new int[n];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		quickSort(a,0,n-1);
		for(int i=0;i<n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}