新疆网站建设友情链接

快速排序的思路是:首先拿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);
}