快速排序的多种思路实现：


两边想中间靠拢：


//两边想中间靠拢，当a[left]<keya[right]>key时，两者交换intPartSortBothSize(int*a,intleft,intright){assert(a!=NULL);intkey=a[right];intbegin=left;intend=right-1;while(begin<end){while(begin<end&&(a[begin]<=key)){++begin;}while(begin<end&&(a[end]>=key)){--end;}if(begin<end){swap(a[begin],a[end]);}}if(a[begin]>a[right]){swap(a[begin],a[right]);returnbegin;}returnright;}

挖坑法：

//挖坑法leftright是坑a[left]>key时将a[left]放到right位置，a[right]<key时，将a[right]放到left位置intPartSortPotholing(int*a,intleft,intright){assert(a!=NULL);intkey=a[right];intbegin=left;intend=right;while(left<right){while(left<right&&a[left]<=key){left++;}if(left<right){a[right]=a[left];right--;}while(left<right&&a[right]>=key){right--;}if(left<right){a[left]=a[right];left++;}}a[left]=key;returnleft;}

顺向

//顺向//left、right从左向右走，当a[left]<key时，left停止，当a[right]>key,right停止，交换两者对应的值intPartSortBothRight(int*a,intleft,intright){assert(a!=NULL);intkey=a[right];intprev=left;while(a[left]<key)//当开始的数字比key小移动left、prev{left++;prev++;}while(left<right){while(left<right&&a[left]>=key){left++;}while(left<right&&a[prev]<=key){prev++;}if(left<right){swap(a[left],a[prev]);left++;prev++;}}swap(a[prev],a[left]);returnprev;}

调用函数：

void_QuickSort(int*a,intleft,intright){assert(a!=NULL);if(left>=right){return;}//intdiv=PartSortBothSize(a,left,right);//intdiv=PartSortPotholing(a,left,right);intdiv=PartSortBothRight(a,left,right);if(div>0){_QuickSort(a,left,div-1);}if(div<right-1){_QuickSort(a,div+1,right);}}voidQuickSort(int*a,size_tsize){assert(a!=NULL);if(size>1){_QuickSort(a,0,size-1);}}

test:

inta4[]={0,5,2,1,5,5,7,8,5,6,9,4,3,5,-2,-4,-1};