学步园

#include <iostream><br /> using namespace std;</p> <p>class QuickSort<br /> {<br /> private:<br /> int *arr;//待排序数组<br /> int length;//数组长度<br /> public:<br /> //构造函数<br /> QuickSort(int length)<br /> {<br /> arr=new int[length+1];<br /> this->length=length;<br /> }<br /> //交换函数<br /> void swap(int i,int j)<br /> {<br /> int temp=arr[i];<br /> arr[i]=arr[j];<br /> arr[j]=temp;<br /> }<br /> //输入数据<br /> void input()<br /> {<br /> int i=1;<br /> while(i<=length)<br /> {<br /> cin>>arr[i];<br /> ++i;<br /> }<br /> }<br /> //输出函数<br /> void display()<br /> {<br /> int i=1;<br /> while(i<=length)<br /> {<br /> cout<<arr[i]<<" ";<br /> ++i;<br /> }<br /> cout<<endl;<br /> }<br /> //随机化划分函数<br /> int randomizedPartition(int start,int end)<br /> {<br /> int i=start+rand()%(end-start+1);//产生随机数start~end<br /> swap(i,start);//交换元素<br /> return partition(start,end);//返回划分位置<br /> }</p> <p> //划分函数<br /> int partition(int start,int end)<br /> {<br /> int key=arr[start];//arr[start]作为划分关键字<br /> int i=start;<br /> int j=end;<br /> //交换元素<br /> while(true)<br /> {<br /> while(arr[i]<key)<br /> {<br /> ++i;<br /> }<br /> while(arr[j]>key)<br /> {<br /> --j;<br /> }<br /> //寻找两个可以交换的元素<br /> //如果j<=i，说明arr[j]在左半域，arr[i]在右半域,划分完成，在j,j+1之间划分<br /> if(i<j)<br /> {<br /> swap(i,j);<br /> ++i;<br /> --j;<br /> }<br /> else<br /> {<br /> return j;<br /> }<br /> }<br /> }<br /> //快速排序<br /> void quickSort(int start,int end)<br /> {<br /> if(start<end)//起码有2个元素<br /> {<br /> int middle;<br /> middle=randomizedPartition(start,end);<br /> quickSort(start,middle);<br /> quickSort(middle+1,end);<br /> }<br /> }<br /> //线性时间选择第k小元素<br /> int randomizedSelect(int start,int end,int k)<br /> {<br /> if(start==end)//如果有两个元素的段被随机化划分之后，则应该有此等式成立，即找到了第K小元素<br /> {<br /> return arr[start];<br /> }<br /> else<br /> {<br /> int middle=randomizedPartition(start,end);<br /> int left=middle-start+1;<br /> if(k<=left)<br /> {<br /> return randomizedSelect(start,middle,k);//在划分后的左侧寻找第k小元素<br /> }<br /> else<br /> {<br /> return randomizedSelect(middle+1,end,k-left);//在划分后的右侧寻找第k-左段长度小的元素<br /> }<br /> }<br /> }<br /> };</p> <p>void main()<br /> {<br /> QuickSort test(10);<br /> test.input();<br /> test.display();<br /> cout<<test.randomizedSelect(1,10,3)<<endl;//寻找第3小元素<br /> test.quickSort(1,10);//随机化快速排序<br /> test.display();//打印结果<br /> }