**

快速排序

**
基本思想：
首先确定一个基准数（一般选取数组第一个值）；
然后通过排序将数组分成以基准数为中心的独立的两部分（即基准数左边的值都比基准数小，基准数右边的值都比基准数大）；
最后再通过递归的方法将基准数左右两边的数组进行排序。

实例讲解：

C++源代码：

#include<stdio.h>
#include<iostream>
using namespace std;

void quickSort(int[], int, int);
int main()
{
	int arr[] = { 34,65,12,43,67,5,78,10,3,70 };
	int len = sizeof(arr) / sizeof(int);
	cout << "排序前arr数组为：" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " , ";
	}
	quickSort(arr, 0, len-1);
	cout << "\n\n排序后arr数组为：" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " , ";
	}

	system("pause");
	return 0;
}

void quickSort(int arr[], int l, int r)
{
	//从右向左找，找第一个比基准数小的数存入到arr[i]，如果不小于基准数，则l--;
	//从左向右找，找第一个比基准数大的数存入到arr[j]，如果不大于基准数，则r++；
	//如此反复进行，直到确定基准数的位置后（也就是在基准数的左边的值都小于基准数，在基准数的右边的值都大于基准数
	//然后再分别递归完成基准数左右两边的数的排序
	if (l < r)
	{
		int i = l, j = r, x = arr[l];
		while (i < j)
		{

			while (i < j && arr[j] >= x)
				j--;
			if (i < j)
				arr[i] = arr[j];
			while (i < j&&arr[i] < x)
				i++;
			if (i < j)
				arr[j] = arr[i];
		}
		arr[i] = x;
		quickSort(arr, l, i - 1);
		quickSort(arr, i + 1, r);
	}
}