随机化快排！求指教~我用C++ 的 stl模版库弄得 但是有两个错误,我调不出来了。麻烦前辈们帮我看看吧C/C++ co
随机化快排！求指教~
我用C++ 的 stl模版库弄得 但是有两个错误,我调不出来了。麻烦前辈们帮我看看吧
C/C++ code#include <cstdlib> #include <ctime>#include <iterator>#include <iostream>#include <algorithm>#include <vector>using namespace std;int randomNumber(int p , int q){ return p+(int)((double)(q-p)*rand()/(RAND_MAX)); //返回随机值}template<typename Iterator , typename Comparator>Iterator randomizedPartition(Iterator p , Iterator r , Comparator comp){ int n = distance(p , r); Iterator q = p , t = r; int i = randomNumber(0 , n-1); //获取一个随即值 advance(q,i); iter_swap(q , --t); //交换迭代器当前的内容 return stable_partition(p , r , bind2nd(comp , *t)); //运用标准模版库里面的序列划分}template<typename Iterator , typename Comparator>void quicksort(Iterator p , Iterator r , Comparator comp){ int n = distance(p , r); if(n>1) { Iterator q = randomizedPartition(p , r , comp); copy(p,r, ostream_iterator<int>(cout, " ")); cout<<endl; quicksort(p , q , comp); quicksort(q , r , comp); }}int main(int argc, char** argv) { int a[] = {6,6}; srand((int)time(0)); vector<int> vb = vector<int>(a,a+2); quicksort(vb.begin() , vb.end(), less<int>()); copy(vb.begin() , vb.end(), ostream_iterator<int>(cout , " ")); system("pause"); return 0;}
错误一：如果我定义的数组里面有相同数字，运行结果就是堆栈溢出，无限刷。
错误二：如果没有相同的数组，能运行，但是输出结果跟我定义的comparator是相反的。
[解决办法]// quicksort3.cpp : 定义控制台应用程序的入口点。
//快速排序程序 张凌康
#include "stdafx.h"
#include<iostream>
#include<ctime>
using namespace std;
void swap(int *values,int i,int j)
{
int temp=values[i];
values[i]=values[j];
values[j]=temp;
}
int partition(int *values,int low,int high)
{
//基本思想，以valuse[high]为标准对（low,high-1）范围内的元素进行划分
//firstbigger为第二部分的第一个元素的下标，也就是大于values[high]那一
//部分的第一个元素的下标，然后将valuse[firstbigger]与values[high]交换，
//则firstbigger为返回值
swap(values,high,rand()%(high-low+1)+low);
int firstbigger=high;
//i为当前考查元素的下标
for(int i=0;i<firstbigger;)
{
while(values[i]<=values[high])
++i;
if(i<firstbigger)
{
--firstbigger;
swap(values,i,firstbigger);
}
}
swap(values,high,firstbigger);
return firstbigger;
}
void quicksort(int *values,int low,int high)
{
if(low<high)
{
int key=partition(values,low,high);
quicksort(values,low,key-1);
quicksort(values,key+1,high);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n=10;
int *values=new int[n];
srand((unsigned)time(NULL));
for(int i=0;i<n;++i)
values[i]=rand()%100;
cout<<"随机产生的数据为：\n";
for(int i=0;i<n;++i)
cout<<values[i]<<" ";
cout<<endl;
quicksort(values,0,n-1);
cout<<"排序后的数据为：\n";
for(int i=0;i<n;++i)
cout<<values[i]<<" ";
cout<<endl;
return 0;
}
[解决办法]http://download.csdn.net/detail/yuanrongceo/2944403
我资源里边有，上边连接自己下吧
