文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>递归与分治策略-----快速排序(C++)

递归与分治策略-----快速排序(C++)

时间:2010-11-16  来源:PhoenixZq

 

template <class T>
int partition(vector<T>& arr,int low,int high)
{
//arr[0]=arr[low];
int pivot=arr[low];
while(low<high){
while(low<high&&arr[high]>=pivot)
--high;
arr[low]=arr[high];
while(low<high&&arr[low]<=pivot)
++low;
arr[high]=arr[low];
}
arr[low]=pivot;
return low;
}

template <class T>
void qSort(vector<T>& arr,int start,int end)
{
int q;
if(start<end){
q=partition(arr,start,end);
qSort(arr,start,q-1);
qSort(arr,q+1,end);
}
}

template <class T>
void DisPlay(vector<T>& arr,int length)
{
for(int k=0;k<length;++k)
cout << arr[k] << " ";
cout << endl;
}

int main()
{
const int length = 20;
vector<int> arr(length);
for (size_t i = 0;i < arr.size(); ++ i)
arr[i] = i;
random_shuffle(arr.begin(),arr.end());

//copy(arr.begin(),arr.end(),ostream_iterator<int>(cout, " "));
//cout << endl;
//int arr[]={2,7,4,1,3,5,9,8,6,10};
//int length=sizeof(arr)/sizeof(arr[0]);
cout << "快速排序前输出: " << endl;
DisPlay(arr,length);

qSort(arr,0,length-1);

//copy(arr.begin(),arr.end(),ostream_iterator<int>(cout, " "));
// cout << endl;

cout << "快速排序后输出: " << endl;
DisPlay(arr,length);
return 0;
}

相关阅读 更多 +
排行榜 更多 +
辰域智控app

辰域智控app

系统工具 下载
网医联盟app

网医联盟app

运动健身 下载
汇丰汇选App

汇丰汇选App

金融理财 下载