急求！！C++高手来，关于排序综合的问题！

回答1：

正好复习一下大一大二学过的东西~~我是学计算机的哦，不过差不多一年没接触排序算法了，竟然忘记得差不多了，花了我半天时间。。。不过你的要求应该基本实现了，我用的是VC6.0。

#include

#include//clock()头文件

#include

#include//文件操作头文件

using namespace std;

#define MAX_NUM 100000//定义系统产生的随机数的最大个数

void srand (unsigned int seed);//申明随机数发生器的初始化函数

int rand(void);//申明伪随机数发生器

void bubbleSort(long b[],long a[],long n){/*冒泡排序*/

for(long i=0;i

a[i]=b[i];//将随机数数组复制一份，使用副本进行运算

for(i=1;i

for(long j=n-1;j>=i;j--){

if(a[j]

long t=a[j];

a[j]=a[j-1];

a[j-1]=t;

}

void insertSort(long b[],long a[],long n){ /*插入排序*/

long i,j,k;

for(i=0;i

a[i]=b[i];//复制随机数数组

for(i=0;i

k=a[i];

for(j=i-1;j>=0&&a[j]>k;j--){

if(a[j]>k)

a[j+1]=a[j];

}

a[j+1]=k;

}

void selectSort(long b[],long a[],long n){/*选择排序*/

long i,j,m,t;

for(i=0;i

a[i]=b[i];//复制随机数组

for(i=0;i

m=i;

for(j=i+1;j

if(a[j]

m=j;

if(m!=i){

t=a[i];

a[i]=a[m];

a[m]=t;

}

void sort(double a[],string c[],int n){/*选择两种最快的排序法*/

for(int i=1;i

for(int j=n-1;j>=i;j--){

if(a[j]

double t=a[j];

string d=c[j];

a[j]=a[j-1];

c[j]=c[j-1];

a[j-1]=t;

c[j-1]=d;

}

void main(){

int i=0,j=0,k=0;

long m;

double compare[3];

string d[]={"冒泡排序","插入排序","选择排序"};

ofstream out;//文件流对象

char s[100000];

clock_t start,end;//定义排序开始及结束时间

char tbuffer[9];

srand((unsigned int)time(NULL));

m=20000+rand();//随机数的个数=20000+系统产生的随机数

long num[MAX_NUM],a[MAX_NUM];

for(i=0;i

num[i]=rand();//将m个随机数赋给num数组，以便进行运算

cout<<"本次测试产生的随机数总数为："<

cout<<"\n.......冒泡排序......."<

cout<<"开始时间："<<_strtime(tbuffer)<

start=clock();

bubbleSort(num,a,m);

end=clock();

cout<<"结束时间："<<_strtime(tbuffer)<

out.open("bubbleSort.txt"); //打开bubbleSort.txt，记录冒泡排序结果

j=0;

for(i=0;i

sprintf(s, "%d\n", a[i]);//将long型整数转换为字符串

out.write(s,strlen(s));//写入文件

}

out.close();

compare[0]=(end-start)/double(CLOCKS_PER_SEC);

cout<<"性能："<

cout<<"排序结果已存入bubbleSort.txt"<

cout<<"\n.......插入排序......."<

cout<<"开始时间："<<_strtime(tbuffer)<

start=clock();

insertSort(num,a,m);

end=clock();

cout<<"结束时间："<<_strtime(tbuffer)<

out.open("insertSort.txt");//打开insertSort.txt，记录插入排序结果

for(i=0;i

sprintf(s, "%d\n", a[i]);

out.write(s,strlen(s));

}

out.close();

compare[1]=(end-start)/double(CLOCKS_PER_SEC);

cout<<"性能："<

cout<<"排序结果已存入insertSort.txt"<

cout<<"\n.......选择排序......."<

cout<<"开始时间："<<_strtime(tbuffer)<

start=clock();

selectSort(num,a,m);

end=clock();

cout<<"结束时间："<<_strtime(tbuffer)<

out.open("selectSort.txt"); //打开selectSort.txt，记录选择排序结果

j=0;

for(i=0;i

sprintf(s, "%d\n", a[i]);

out.write(s,strlen(s));

}

out.close();

compare[2]=(end-start)/double(CLOCKS_PER_SEC);

cout<<"性能："<

cout<<"排序结果已存入selectSort.txt"<

sort(compare,d,3);//调用sort()，计算出两种较快的排序方法

cout<<"\n***本次测试中最快的两种排序方法为:\n1."<

}

回答2：

// cv.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#include"time.h"

/***************************************************************************************
冒泡排序
****************************************************************************************/
long Bubblesort(long R[],long n)
{
int flag=1;
long BC=0;
for(long i=1;i {
flag=0;
for(long j=n-1;j>=i;j--)
{
if(R[j] {
long t=R[j];
R[j]=R[j-1];
R[j-1]=t;
flag=1;
BC++; //交换次数
}

}
}
return BC;
}

long Bubblesortcompare(long R[],long n)
{
int flag=1;
long BC=0;
for(long i=1;i {
flag=0;
for(long j=n-1;j>=i;j--)
{
if(R[j] {
long t=R[j];
R[j]=R[j-1];
R[j-1]=t;
flag=1;
BC++;
}
if(R[j]>=R[j-1])
BC++; //比较次数

}
}
return BC;
}

/***************************************************************************************
选择排序
****************************************************************************************/
long selectsort(long R[],long n)
{
long i,j,m;
long t,SC=0;
for(i=0;i {
m=i;
for(j=i+1;j {
if(R[j] {m=j;}
if(m!=i)
{
t=R[i];
R[i]=R[m];
R[m]=t;
SC++;//交换次数
}
}

}
return SC;
}

long selectsortcompare(long R[],long n)
{
long i,j,m;
long t,SC=0;
for(i=0;i {
m=i;
for(j=i+1;j {
if(R[j]>=R[m])
{
SC++;

}
if(R[j] {
m=j;
SC++;
}
if(m!=i)
{
t=R[i];
R[i]=R[m];
R[m]=t;

}
}

}

return SC;
}

/***************************************************************************************
直接插入排序
****************************************************************************************/
long insertsort(long R[],long n)
{
long IC=0;
for(long i=1;i {
long temp=R[i]; //把待排序元素赋给temp
long j=i-1;
while((j>=0)&&(temp {
R[j+1]=R[j]; //顺序比较和移动
j--;
IC++;
}
IC++;//交换次数
R[j+1]=temp;
}
return IC;
}

long insertsortcompare(long R[],long n)
{
long IC=0;
for(long i=1;i {

long temp=R[i]; //把待排序元素赋给temp
long j=i-1;
while((j>=0)&&(temp {
if(temp>=R[j])
{
IC++;
}
R[j+1]=R[j]; //顺序比较和移动
j--;IC++;//比较次数

}
R[j+1]=temp;
}
return IC;
}

/***************************************************************************************
希尔排序
****************************************************************************************/
long ShellSort(long R[],long n)
{
int temp,SC=0;
for(int i=n/2;i>0;i/=2) //将所有记录分成增量为t的子序列
{
for(int j=0;j for(int k=j+i;k for(int p=j;p if(R[k] {
temp=R[k];
for(int q=k;q>p;q-=i) //插入位置以后的记录依次后移
{
R[q]=R[q-i];
SC++;
}
R[p]=temp; //插入记录
break;
}
}
return SC;
}

long ShellSortcompare(long R[],long n)
{
int temp,SC=0;
for(int i=n/2;i>0;i/=2) //将所有记录分成增量为t的子序列
{
for(int j=0;j for(int k=j+i;k for(int p=j;p { if(R[k]>=R[p])
SC++;
if(R[k] {SC++;
temp=R[k];
for(int q=k;q>p;q-=i) //插入位置以后的记录依次后移
{
R[q]=R[q-i];

}
R[p]=temp; //插入记录
break;
}}
}
return SC;
}

/***************************************************************************************
快速排序
****************************************************************************************/
long quicksort(long R[],long left,long right)
{
static long QC=0;
long i=left,j=right;
long temp=R[i];
while(i {
while((R[j]>temp)&&(j>i))
{
QC++;
j=j-1;
}
if(j>i)
{
R[i]=R[j];
i=i+1;
QC++;
}
while((R[i]<=temp)&&(j>i))
{
QC++;
i=i+1;
}
if(i {
R[j]=R[i];
j=j-1;
QC++;
}
}
//二次划分得到基准值的正确位置
R[i]=temp;
if(left quicksort(R,left,i-1); //递归调用左子区间
if(i+1 quicksort(R,i+1,right); //递归调用右子区间
return QC;
}

long quicksortcompare(long R[],long left,long right)
{
static long QC=0;
long i=left,j=right;
long temp=R[i];
while(i {
while((R[j]>temp)&&(j>i))
{
QC++;
j=j-1;
}
if(j>i)
{
R[i]=R[j];
i=i+1;
}
while((R[i]<=temp)&&(j>i))
{
QC++;
i=i+1;
}
if(i {
R[j]=R[i];
j=j-1;
}
}
//二次划分得到基准值的正确位置
R[i]=temp;
if(left quicksort(R,left,i-1); //递归调用左子区间
if(i+1 quicksort(R,i+1,right); //递归调用右子区间
return QC;
}

/***************************************************************************************
堆排序
****************************************************************************************/
static long HC=0;
void Heap(long R[],int n) //重新构造小顶堆
{
int temp;
for(int i=0;i*2 {
if(R[i]>=R[2*i]&&R[2*i])
{
temp=R[i];
R[i]=R[2*i];
R[2*i]=temp;
HC++;
}
if(R[i]>=R[2*i+1]&&R[2*i+1])
{
temp=R[i];
R[i]=R[2*i+1];
R[2*i+1]=temp;
HC++;
}
}
}
long HeapSort(long R[],int n) //取出堆顶
{
for(int i=n-1;i>=0;i--)
{
Heap(R,i);
R[0]=R[i];
}
return HC;
}

long HeapSortcompare(long R[],int n) //取出堆顶
{
for(int i=n-1;i>=0;i--)
{
Heap(R,i);
R[0]=R[i];
}
return HC;
}

/***************************************************************************************
操作选择函数
****************************************************************************************/
void operate(long a[],long n)
{
long*R=new long[n];
time_t start,end;
double dif;
long degree,compare;
char ch;
cout<<"请选择排序算法：\t";
cin>>ch;
switch(ch){
case'1':
{
int i;
for(i=0;i {
R[i]=a[i];
}
time(&start);
degree=Bubblesort(R,n);

time(&end);
dif=difftime(end,start);

cout<<"冒泡排序交换次数：\t"< for(i=0;i {
R[i]=a[i];
}
compare=Bubblesortcompare(R,n);
cout<<"冒泡排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'2':
{
int i;
for(i=0;i {
R[i]=a[i];
}
time(&start);
degree=selectsort(R,n);
for(i=0;i {
R[i]=a[i];
}
compare=selectsortcompare(R,n);
time(&end);
dif=difftime(end,start);

cout<<"选择排序交换次数：\t"< cout<<"选择排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'3':
{ int i;
for( i=0;i {
R[i]=a[i];
}
time(&start);
degree=insertsort(R,n);
time(&end);
dif=difftime(end,start);
cout<<"插入排序交换次数：\t"< for(i=0;i {
R[i]=a[i];
}
compare=insertsortcompare(R,n);
cout<<"插入排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'4':
{ int i;
for(i=0;i {
R[i]=a[i];
}
time(&start);
degree=ShellSort(R,n);
for(i=0;i {
R[i]=a[i];
}
compare=ShellSortcompare(R,n);
time(&end);
dif=difftime(end,start);

cout<<"希尔排序交换次数：\t"< cout<<"希尔排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'5':
{ int i;
for(i=0;i {
R[i]=a[i];
}
time(&start);
degree=quicksort(R,0,n-1);
time(&end);
dif=difftime(end,start);
cout<<"快速排序交换次数：\t"< for(i=0;i {
R[i]=a[i];
}
compare=quicksortcompare(R,0,n-1);
cout<<"快速排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'6':
{
for(int i=0;i {
R[i]=a[i];
}
time(&start);
degree=HeapSort(R,n);
compare=HeapSortcompare(R,n);
time(&end);
dif=difftime(end,start);

cout<<"堆排序交换次数：\t"< cout<<"堆排序比较次数：\t"< cout<<'\n';
operate(a,n);
break;
}
case'7':
break;
default:
{
cout<<"输入错误，请选择正确操作!"<<'\n';
break;
}
}
}

int main(int argc, char* argv[])
{
long n;
char check;
cout<<"\n** 排序算法比较 **"< cout<<"============================================"< cout<<"*** 1---冒泡排序 ***"< cout<<"*** 2---选择排序 ***"< cout<<"*** 3---直接插入排序 ***"< cout<<"*** 4---希尔排序 ***"< cout<<"*** 5---快速排序 ***"< cout<<"*** 6---堆排序 ***"< cout<<"*** 7---退出程序 ***"< cout<<"============================================"<
while(1)
{
cout<<"\n请输入要产生随机数的个数：";
long n;
cin>>n;
cout< long*a=new long[n];
srand((unsigned long)time(NULL));
for(long i=0;i {
a[i]=rand()%n;
}
operate(a,n);
cout<<"是否重复实验?\n继续请按y\n退出请按n\n请输入您的选择:\t\t";
cin>>check;
if(check=='y'||check=='Y')
continue;
if(check=='n'||check=='N')
break;
}

}

回答3：

#include
#include
#include
#include
using namespace std;

#define DATA 40 //数组元素个数

template
void Swap(T & a,T & b)
{
T temp;
temp=a;
a=b;
b=temp;
}

//冒泡法排序
template
void BubbleSort(T A[], int n)
{
int i,j,last;
i=n-1;
while (i>0)
{ //最多进行n-1趟
last=0; //进入循环就将last置成0
for (j=0; j if (A[j+1] {
Swap(A[j],A[j+1]); //由于后者小，故交换
last=j; //有交换就将last置成j
}
i=last; //如果一趟排序中没有交换元素，则last为0
}
}

//两路合并法排序
template
void Merge(T a[],int i1,int j1,int i2,int j2)
{ // i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界
T *Temp=new T[j2-i1+1]; //分配能存放两个子序列的临时数组
int i=i1,j=i2,k=0; //i,j是两个子序列的游动指针，k是Temp的游动指针
while (i<=j1&&j<=j2) //若两个子序列都不空，则循环
if (a[i]<=a[j]) Temp[k++]=a[i++]; //将A[i]和A[j]中较小的存入Temp[k]
else Temp[k++]=a[j++];
while (i<=j1)
Temp[k++]=a[i++]; //若第一个子序列中还有剩余的就存入Temp
while (j<=j2)
Temp[k++]=a[j++]; //若第二个子序列中还有剩余的就存入Temp
for (i=0; i a[i1++]=Temp[i]; //将临时数组中的元素倒回A
delete [] Temp;
}

template
void MergeSort(T a[], int n)
{
int i1,j1,i2,j2; //i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界
int size=1; //子序列中元素个数，初始化为1。
while (size {
i1=0;
while (i1+size { //若i1+size i2=i1+size; //确定子序列2的下界
j1=i2-1; //确定子序列1的上界
if (i2+size-1>n-1)
j2=n-1; //若第2个子序列中不足size个元素，则置子序列2的上界j2=n-1
else
j2=i2+size-1; //否则有size个，置j2=i2+size-1
Merge(a,i1,j1,i2,j2); //合并相邻两个子序列
i1=j2+1; //确定下一次合并第一个子序列的下界
}
size*=2; //元素个数扩大一倍
}
}

int main()
{

int p,l;
double m,n;
clock_t clock_start=clock();
clock_t clock_end;
int *a,b[DATA];
a=b;
for(p=0;p<2;p++)
{
clock_start=clock();
srand(time(0));
if (p==0)
{
double x;
for(l=0;l<10000;l++)
{
for(int j=0;j a[j]=rand()%200;
BubbleSort(a,DATA);
}
clock_end=clock();
cout<<"//***************冒泡排序法******************//"<<'\n';
cout< for(int e=0;e {
cout< }
cout<<"starttime:"< cout<<"finishtime:"< cout<<"10000 次运行时间:"< x=clock_end-clock_start;
m=x/10000;
cout<<"冒泡法排序平均时间:"< }
if (p==1)
{
double y;
for(l=0;l<10000;l++)
{
for(int j=0;j a[j]=rand()%200;
MergeSort(a,DATA);

}
cout<<"//****************两路合并排序法*******************//"<<'\n';
cout< clock_end=clock();
for(int e=0;e {
cout< }
cout<<"starttime:"< cout<<"finishtime:"< cout<<"10000 次运行时间:"< y=clock_end-clock_start;
n=y/10000;
cout<<"两路合并平均时间:"< cout<<"//************排序比较结果**************//"<<'\n';
}

}
if(m>n)
cout<<"两路合并排序更快!"< else
cout<<"冒泡法排序更快!"< return 0;
}

回答4：

//visual studio 2005中编译通过
#include
#include
#include

using namespace std;

void QSort(int *a,int b,int e) /*快速排序*/
{
int l=b,r=e,k=a[b];

if (b while (l {
while (lk)
r--;
if (l
while (l l++;

if (l
}
a[l]=k;
QSort(a,b,l-1);
QSort(a,l+1,e);
}
}

void SelectSort(int *a,int n) /*选择排序*/
{
int i,j,k;
for (i = 0; i k=i;
for (j=i+1; j if (a[k]>a[j]) k=j;
if (k!=i) {
j=a[k];
a[k]=a[i];
a[i]=j;
}
}
}

void InsertSort(int *a,int n) /*插入排序*/
{
int i,j,k;
for (i = 0; i k=a[i];
for (j=i-1; j>=0&&a[j]>k; j--) {
if (a[j]>k) {
a[j+1]=a[j];
}
}
a[j+1]=k;
}
}

void QuickSort(int *pData,int left,int right) //快速排序
{
int i(left),j(right),middle,iTemp;
//middle=pData[(left+right)/2];//求中间值
middle=pData[(rand()%(right-left+1))+left];//生成大于等于left小于等于right的随机数
do{
while((pData[i] i++;
while((pData[j]>middle) && (j>left))//从右扫描小于中值的数
j--;//找到了一对值,交换
if(i<=j){
iTemp=pData[j];
pData[j]=pData[i];pData[i]=iTemp;i++;j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left if(lefti)，递归右半边
if(right>i){QuickSort(pData,i,right);}
}
void BubbleUpSort(int *pData,int nCount)//冒泡排序法
{
int nTmp;
for(int i=0;i for(int j=i+1;j if(pData[i]>pData[j]){
nTmp=pData[i];pData[i]=pData[j];pData[j]=nTmp;
}
}
void InitArray(int *pData,int nCount)
{
srand( (unsigned)time(NULL));
for(int i=0;i}
void ShowArray(int *pData,int nCount)
{
for(int i=0;i cout< if((i+1)%10==0)cout< }
}
int main()
{
__int64 t1, t2;
const int nCount=20000;
int *pData=new int[nCount];

InitArray(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t1));
QSort(pData,0,nCount-1);
GetSystemTimeAsFileTime(LPFILETIME(&t2));
//ShowArray(pData,nCount);
//显示排序后的结果，这里并不计算时间，如果只是比较时间，这里可以注掉
printf( "快速排序法经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );

InitArray(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t1));
BubbleUpSort(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t2));
//ShowArray(pData,nCount);
printf( "冒泡法经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );

InitArray(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t1));
SelectSort(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t2));
//ShowArray(pData,nCount);
printf( "选择排序经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );

InitArray(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t1));
InsertSort(pData,nCount);
GetSystemTimeAsFileTime(LPFILETIME(&t2));
//ShowArray(pData,nCount);
printf( "插入排序经过了%I64d.%04I64d毫秒\n", (t2-t1)/10000, (t2-t1)%10000 );
delete [] pData;
cin.get();//停住，以看清结果
return 0;
}
//参照了匿名回答者，但时间精确到了0.0001毫秒。

回答5：

//---------------------------------------------------------------------------

#include
#include
#include

void Qsort(int *a,int b,int e) /*快速排序*/
{
int l=b,r=e,k=a[b];

if (b while (l {
while (lk)
r--;
if (l
while (l l++;

if (l
}
a[l]=k;
Qsort(a,b,l-1);
Qsort(a,l+1,e);
}
}

void ssort(int *a,int n) /*选择排序*/
{
int i,j,k;
for (i = 0; i k=i;
for (j=i+1; j if (a[k]>a[j]) k=j;
if (k!=i) {
j=a[k];
a[k]=a[i];
a[i]=j;
}
}
}

void isort(int *a,int n) /*插入排序*/
{
int i,j,k;
for (i = 0; i k=a[i];
for (j=i-1; j>=0&&a[j]>k; j--) {
if (a[j]>k) {
a[j+1]=a[j];
}
}
a[j+1]=k;
}
}

int *init(const int n) /*初始化函数，返回含有n个随机整数的数组*/
{
static int st=0,*a=NULL;
int i;
if (!st) {
srand(time(NULL));
st=1;
if ((a=(int *)malloc(sizeof(int)*n))==NULL) {
fprintf(stderr,"ERROR\n");
exit(-1);
}
}

for (i = 0; i a[i]=rand();
}
return a;

}
int main(int argc, char* argv[])
{
time_t b,e;
int *a;
int N=20000; /*测试数据的规模*/

/*测试选择排序算法对N个整数排序所用时间*/
a=init(N);
b=time(NULL);
ssort(a,N);
e=time(NULL);
printf("Select Sort: %d sec.\n\n",e-b);

/*测试插入排序算法对N个整数排序所用时间*/
a=init(N);
b=time(NULL);
isort(a,N);
e=time(NULL);
printf("Insert Sort: %d sec.\n\n",e-b);

/*测试快速排序算法对N个整数排序所用时间*/
a=init(N);
b=time(NULL);
Qsort(a,0,N-1);
e=time(NULL);
printf("Quick Sort: %d sec.\n\n",e-b);

free(a);
return 0;
}
//---------------------------------------------------------------------------