快速排序是冒泡排序的一种改进。（冒泡排序是比较相邻的数，并使小的在前大的在后）
核心思想为：每一趟排序都选取一个基准数，将数据通过基准数分割成独立的两部分，左边部分的数小于右边部分的数，且在一趟排序完成后使基准数在正确的位置上。
目前有两种选择基准数的方法。
1.标准快排：选取数组第一个数为基准数。（这种方法的缺点在于对于基本有序的序列排序反而很慢）
2.改进快排：选取数组中间的数为基准数，比普通快排要快一些。
方法一代码如下
#include <bits/stdc++.h>
using namespace std;
int a[100005],n;
void qsort(int low, int high)
{
if (high <= low) return;
int i = low;
int j = high + 1;
//开头的数为基准数
int key = a[low];
while (true)
{
/*从左向右找比key大的值*/
while (a[++i] < key)
{
if (i == high){
break;
}
}
/*从右向左找比key小的值*/
while (a[--j] > key)
{
if (j == low){
break;
}
}
if (i >= j) break;
/*交换i,j对应的值*/
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//基准数与j对应值交换,因为与基准数交换位置后在其前面，所以交换的数要比基准数小，所以选j
int temp = a[low];
a[low] = a[j];
a[j] = temp;
qsort(low, j - 1);
qsort(j + 1, high);
}
int main()
{
cin>>n;
int item;
for(int i = 0 ; i < n ; i++)
{
cin>>item;
a[i] = item;
}
qsort(0,n-1);
for(int i = 0 ; i < n - 1 ; i++)
{
cout << a[i] << " ";
}
cout<<a[n-1]<<endl;
return 0;
}
方法二代码如下
void qsort(int l,int r)
{
int mid=a[(l+r)/2];//基准数
int i=l,j=r;
do{
while(a[i]<mid) i++;//查找左半部分比中间数大的数，到mid就停止
while(a[j]>mid) j--;//查找右半部分比中间数小的数，到mid就停止
if(i<=j)//如果有一组不满足排序条件（左小右大）的数，这里注意要有=
{
swap(a[i],a[j]);
i++;
j--;
}
}while(i<=j);//这里注意要有=
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
