学步园

自己写的快速排序模板。:-)。

第一种是常规形式，第二种加入了随机化数。

#include "time.h"<br /> #include <algorithm><br /> #include <iostream><br /> using namespace std;<br /> const int max_n=300;<br /> void quick_sort(int a[],int first,int last)<br /> {<br /> int left=first,right=last;<br /> int temp=a[first];<br /> while(left<right)<br /> {<br /> while(left<right&&a[right]>=temp) right--;<br /> a[left]=a[right];<br /> while(left<right&&a[left]<temp) left++;<br /> a[right]=a[left];<br /> }<br /> a[left]=temp;//此时left=right<br /> if(left-1>first) quick_sort(a,first,left-1);<br /> if(right+1<last) quick_sort(a,right+1,last);<br /> }<br /> void quick_sort2(int a[],int first,int last)<br /> {<br /> int left=first,right=last;<br /> int temp=a[first+rand()%(last-first+1)];<br /> while(1)<br /> {<br /> while(a[left]<temp) left++;<br /> while(a[right]>=temp) right--;<br /> if(left<right)<br /> {<br /> int temp2=a[left];<br /> a[left]=a[right];<br /> a[right]=temp2;<br /> }<br /> else break;<br /> }<br /> //此时left-right=1<br /> if(left-1>first) quick_sort2(a,first,left-1);<br /> if(right+1<last) quick_sort2(a,right+1,last);<br /> }<br /> int main()<br /> {<br /> int pos[max_n],pos2[max_n],pos3[max_n];<br /> srand((unsigned)time(NULL));<br /> for(int i=0;i<max_n;i++)<br /> {<br /> pos[i]=pos2[i]=pos3[i]=rand();<br /> }<br /> quick_sort(pos,0,max_n-1);<br /> quick_sort(pos2,0,max_n-1);<br /> sort(pos3,pos3+max_n);<br /> for(int i=0;i<max_n;i++)<br /> {<br /> printf("%d %d %d/n",pos[i],pos2[i],pos3[i]);<br /> }<br /> return 0;<br /> }