还是C++排序问题

发布网友

我来回答

共2个回答

热心网友

//vc6.0测试通过
//你的快速排序函数有问题,好好看看我的
//你的成员函数定义的时候都没加类的作用域Sort::
#include <iostream>
using namespace std;

#include <iostream>
#include <stdlib.h>
#include <ctime>

#define Max_Num 20000

class Sort
{
public:
Sort(){}
~Sort(){}
void random(int a[],int n);
void BubbleSort(int a[],int n);
void QuickSort(int *a, int n);
void InsertSort(int *a, int n) ;
void DisplayInfo(int a[],int n);
};

void Sort::random(int a[],int n)
{
for(int i=0;i<n;i++)
a[i]=rand()%60000000;
}

void Sort::BubbleSort(int a[],int n)
{
int flag=0; //冒泡
do{
flag=0;
for(int i=1;i<n;i++){
if(a[i]>a[i-1]){
flag=1;
int k=a[i];
a[i]=a[i-1];
a[i-1]=k;
}
}
}while(flag==1);
}
void Sort::QuickSort(int* a, int n)
{
if(n<=1)return;
if (n==2){
if(a[1]<a[0])swap(a[1],a[0]);
return;
}
swap(a[0],a[n/2]);
int* L=a+1;
int* R=a+n-1;
int pivot=a[0];
while(L<R){
while(*L<pivot&&L<R)++L;
while(*R>=pivot&&R>a)--R;
if(L<R)swap(*L,*R);
}
if(*R<pivot)swap(a[0],*R);
QuickSort(a,R-a);
QuickSort(R+1,n-1-(R-a));
}

void Sort::InsertSort(int *a, int n)
{
for(int i=0;i<n;i++){
int k=i;
for(int j=i+1;j<n;++j){
if(a[k]<a[j]) k=j;
}
int num=a[i];
a[i]=a[k];
a[k]=num;
}
}

void Sort::DisplayInfo(int a[],int n)
{
for(int k=0;k<10;k++)cout<<a[k]<<" ";
cout<<endl<<"......."<<endl;
for(int i=0;i<10;i++)cout<<a[n-11+i]<<" ";
cout<<endl;
}
int main()
{
srand(time(0));
int a[Max_Num];
Sort st;
int starttime=0;
int stoptime=0;
int usetime=-1;

starttime=clock();//取CPU当前时间 unix系统下单位是微秒,windows好像是毫秒
st.random(a,Max_Num);
stoptime=clock();
usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<endl;
cout<<"randtime:"<<usetime<<endl;
cout<<endl;
starttime=clock();//取CPU当前时间
st.BubbleSort(a,Max_Num);
stoptime=clock();
usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<"BubbleSorttime:"<<usetime<<endl;

cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
starttime=clock();//取CPU当前时间
st.random(a,Max_Num);
stoptime=clock();
usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<endl;
cout<<"randtime:"<<usetime<<endl;
cout<<endl;
starttime=clock();//取CPU当前时间
st.InsertSort(a,Max_Num);
stoptime=clock();
usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<"InsertSorttime:"<<usetime<<endl;

cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"---------------------------------------------------------"<<endl;
starttime=clock();//取CPU当前时间
st.random(a,Max_Num);
stoptime=clock();

usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<endl;
cout<<"randtime:"<<usetime<<endl;
cout<<endl;
starttime=clock();//取CPU当前时间
st.QuickSort(a,Max_Num);
stoptime=clock();
usetime=stoptime-starttime;
st.DisplayInfo(a,Max_Num);
cout<<"QuickSorttime:"<<usetime<<endl;
return 0;
}追问嗯，高手！赞一个啊！不过那个统计时间的好复杂啊，看下能不能像这个程序类似这样统计时间呢？？我不会加进去，如果你可以的话试下吧：
#include
#include
void main()
{
unsigned long start,end;
long int i=0;
start=GetTickCount();
while(1)
{
i++;
if(i>100000000)
{
break;
}

}
end=GetTickCount();
cout<<end-start<<endl;
}

热心网友

你不是已经写了排序的方法了么？
产生随机数的方法是：srand(time(0));
for( int i = 0 ; i < 20000 ; i++ )
a[n] = rand();追问主函数不会写啦，能否帮忙写下？O(∩_∩)O谢谢啦~~