#include<stdio.h>
#include<stdlib.h>
/**
* 快速排序
基本思想：通过对数组不断地划分，达到排序地目的
划分：任意选择一个元素，将数组一分为二，左边的都小于它，右边的都大于它
*/
int a[]={4,5,6,8,2,1,54,6,8,4,654,6,231,3,878,54,54,878,65,22,4,13,467,36687,5,5,4,6,3,8,4578,5,1,187,8,64,64,84,54,87,8764,231,48,415648,42,132,14,4,984,1,1,54,6,51,3212,3486498};
//int a[]={4,5,6,8,2,1,54};
void switch_(int i ,int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
//划分 返回划分元素最后所在的位置
int partition(int m,int p)
{
int v = a[m]; //划分元素
int i = m; //左边
int j = p; //右边
while(i < j )
{
while(a[i] <= v && i < j) //从左边找到一个元素大于划分元素
{
i++;
}
while(a[j] >= v && j > i) //从右边找到一个小于划分元素的元素，
{
j--;
}
//交换两个元素的位置
if( i < j)
switch_(i,j);
}
//到此 i=j
a[m] = a[j];
a[j] = v;
return j;
}
void printAll()
{
int k = sizeof(a)/sizeof(a[0]);
for(int i = 0 ; i < k ;i++)
{
printf("%d ",a[i]);
}
}
void quickSort(int p,int q)
{
if(p < q)
{
int j = partition(p,q);
//中间那个元素可以不用管了，因为已经固定了，后面的排序不会影响中间的那个元素
quickSort(p,j-1); //继续排序左边
quickSort(j+1,q); //继续排序右边
}
}
void main()
{
int k = sizeof(a) / sizeof(a[0]);
quickSort(0,k-1);
printAll();
}
