快速排序的三种方法（递归方式）
void swap(int *a,int *b) { int tmp=*a; *a=*b; *b=tmp; } int QuickSort1(int arr[],int start,int end,int n)//左右交换 { int index=arr[end]; while(start<end) { while(start<end&&arr[start]<index) start++; while(start<end&&arr[end]>index) end--; swap(&arr[start],&arr[end]); } swap(&index,&arr[start]); return end; } int QuickSort1(int arr[],int start,int end,int n)//挖坑法 { int index=arr[end]; while(start<end) { while(start<end&&arr[start]<index) start++; arr[end]=arr[start]; while(start<end&&arr[end]>index) end--; arr[start]=arr[end]; } arr[end]=index; return end; } int QuickSort1(int arr[],int start,int end,int n)//前后指针法 { if(arr==NULL||start<0||end>n) { return 0; } int small=start-1; int index=arr[end]; swap(&arr[index],&arr[end]); for(index=start;index<end;index++) { if(arr[index]<arr[end]) { ++small; if(index!=small) { swap(&arr[small],&arr[index]); } } } ++small; swap(&arr[small],&arr[end]); return small; } void QuickSort(int arr[],int start,int end,int n) { if(start==end) { return; } int index=QuickSort1(arr,start,end,n); if(index>0) QuickSort(arr,start,index-1,n); if(index<end) QuickSort(arr,index+1,end,n); } int main() { int arr[]={3,6,1,5,2,7,4}; int n=sizeof(arr)/sizeof(int); printf("%d\n",n); for(int i=0;i<n;i++) { printf("%d ",arr[i]); } printf("\n"); //Bubblesort(arr,n); QuickSort(arr,0,n-1,n); //InsertSort(arr,n); //SelectSort(arr,n); //ShellSort(arr,n); for(int i=0;i<n;i++) { printf("%d ",arr[i]); } printf("\n"); return 0; }
