快速排序的思路是:首先拿a[start]作为轴，将原数组中比a[start]小的放small数组，将原数组中比a[start]大的放big数组，最后在将small数组 和a[start]值和big数组中的数复制回原数组。以此递归，使数组逐渐有序。

快速排序的平均时间复杂度是nlogn。

#include<stdio.h>

#include<stdlib.h>

#define N 1000000

int array[N];

int small[N];

int big[N];

void init_array(int a[],int n);

void print_array(int a[],int n);

void quick_sort(int a[],int start,int end);

void Quick_sort(int a[],int n);

int main()

{

 init_array(array,N);

 //quick_sort(array,0,N-1);

 Quick_sort(array,N);

 print_array(array,N); 

}

void init_array(int a[],int n)

{

 int i;

 for(i=0;i<n;i++)

  a[i]=rand()%1000; 

}

void print_array(int a[],int n)

{

 int i;

 for(i=0;i<n;i++)

  printf("%d\n",a[i]); 

}

void Quick_sort(int a[],int n)

{

 quick_sort(a,0,n-1); 

}

void quick_sort(int a[],int start,int end)

{

 if(start>=end) return;

 int mid;

 int temp,i,j=0,k=0;

 temp=a[start];

 for(i=start+1;i<=end;i++) 

 {

  if(a[i]<=temp)

  {

   small[j++]=a[i]; 

  } 

  else

  {

   big[k++]=a[i];

  }

 } 

 mid=start+j;

 for(i=0;i<j;i++)

 {

  a[start+i]=small[i];

 }

 a[mid]=temp;

 for(i=0;i<k;i++)

 {

  a[mid+1+i]=big[i];

 } 

 quick_sort(a,start,mid-1);

 quick_sort(a,mid+1,end);

}