快速排序
每次选择一个数为中间值，将数比该数小的数放在该数左边，比该数大的数放在该数右边，再重复对该数左右两边的数进行该操作，直到所有数都排列完毕。
例：
int a[10]={1,465,31,59,18,67,95,16,20,6};
我们选定6为中间数
第一次排序：
1,6,31,59,18,67,95,16,20,465
对6左边数进行排序结果不变：
1,6,31,59,18,67,95,16,20,465
对6右边数进行排序，选择465做中间数,结果不变：
1,6,31,59,18,67,95,16,20,465
对中间数465左边排序，选20为中间数：
18换31：
1,6,18,59,31,67,95,16,20,465
16换59：
1,6,18,16,31,67,95,59,20,465
20换31：
1,6,18,16,20,67,95,59,31,465
对20左边数排序，选16作为中间数：
16换18
1,6,16,18,20,67,95,59,31,465
对20右边数排序，选31作为中间数：
31换67：
1,6,16,18,20,31,95,59,67,465
对31左边排序，左边顺序正确
对31右边数排序，选67作为中间数：
59换95：
1,6,16,18,20,31,59,95,67,465
95换67：
1,6,16,18,20,31,59,67,95,465
至此，全部排列完成
例：
#include<stdio.h>
int QuickSort(int a[],int left,int right)
{
int i=left,j=left;
int temp=0;
for(;i<right;i++)//i负责遍历数组，j指向数组最左边，每找到一个数就+1
{
if(a[i]<a[right])//i遍历到一个数小于a[right]，即中间数
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
j++; //找到小数后将该数换到j记录的左边位置，然后j右移一个位置，等待下一个小数
}
}
temp=a[right];//遍历完数组，所有的小数都被找到并放在左边，但中间数还在数组最右端，因此将中间数换到中间，也就是j记录的位置
a[right]=a[j];
a[j]=temp;
for(int i=0;i<10;i++)
{
printf("%d ",a[i]);
if(i==j)printf("|");
}
printf("j:%d\n",j);
return j;//返回中间值位置j
}
void sort(int a[],int left,int right)
{
if(left<right)//先判断该需要排列区间的左边界left与右边界right是否相交，不相交代表该区间可以继续排序
{
int temp=QuickSort(a,left,right);//先进行一次排序，分割出两个区间
sort(a,left,temp-1);//对中间数左边的区间进行排序
sort(a,temp+1,right);//对中间数右边的区间进行排序
}
}
int main()
{
int a[10]={1,465,31,59,18,67,95,16,20,6};
sort(a,0,sizeof(a)/sizeof(a[0])-1);
for(int i=0;i<10;i++)
{
printf("%d\t",a[i]);
}
return 0;
}
运行结果如图，被框起的就是每次的中间数，默认为区间最右边的数，加粗地方为被分割出的待排序空间
①：主函数调用的sort：
1 |6|31 59 18 67 95 16 20 465 j:1
②：主函数调用的sort中的sort(a,left,temp-1)：[1]left<right不成立，不进行迭代
③：主函数调用的sort中的sort(a,temp+1,right)：[31,59,18,67,95,16,20,465]
1 6 31 59 18 67 95 16 20 |465 | j:9
④：主函数调用的sort中的sort(a,temp+1,right)中的sort(a,left,temp-1)：[31,59,18,67,95,16,20]
1 6 18 16 |20|67 95 59 31 465 j:4
⑤：主函数调用的sort中的sort(a,temp+1,right)中的sort(a,left,temp-1)中的sort(a,left,temp-1)：[18,16]
1 6 |16|18 20 67 95 59 31 465 j:2 之后不满足left<right不成立，不进行迭代
⑥：主函数调用的sort中的sort(a,temp+1,right)中的sort(a,left,temp-1)中的sort(a,temp+1,right)：[67,95,59,31]
1 6 16 18 20 |31|95 59 67 465 j:5 左区间不满足left<right，迭代右区间
⑦：主函数调用的sort中的sort(a,temp+1,right)中的sort(a,left,temp-1)中的sort(a,temp+1,right)中的sort(a,temp+1,right)：[95，59，67]
1 6 16 18 20 31 59 |67|95 465 j:7 全部排列完成
1 6 16 18 20 31 59 67 95 465
如图：
