📄 四种排序的比较.txt
字号:
#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include "show.h"
#include "math.h"
#include "stdio.h"
#define T int
void Exchange(int & number1,int & number2)
{
int space;
space=number1;
number1=number2;
number2=space;
}
//快速排序
int QuickSort(int * data,int n)
{
int from=0;
int to=n-1;
int middle;
int position=0;
int count=0;
if(n<=1)
return 0;
while(from<to)
{
if(from==position)
{
if(data[position]<data[to])
{
to--;
}
else if(data[position]>data[to])
{
Exchange(data[position],data[to]);
count+=3;
position=to;
from++;
}
else if(data[position]==data[to])
{
to--;
}
}
else if(position==to)
{
if(data[from]>data[position])
{
Exchange(data[position],data[from]);
count+=3;
position=from;
to--;
}
else if(data[from]<data[position])
{
from++;
}
else if(data[from]==data[position])
{
from++;
}
}
}
for(int j=0;j<n;j++)
cout<<data[j]<<' ';
cout<<endl;
middle=position;
count+=QuickSort(data,middle);
count+=QuickSort(data+middle+1,n-middle-1);
return count;
}
//归并排序
int MergeSort(int Data[],int n)
{
int swap;
int count=0;
int * divide;
//传递终止条件
if(n==1)
return 0;
//对数据进行分割
divide=Data+n-n/2;
count+=MergeSort(Data,n-n/2);
count+=MergeSort(divide,n/2);
//合并数据并排序
for(int i=0;i<n/2;i++)
{
for(int j=n-n/2-1+i;j>=0;j--)
if(Data[j]<divide[i])
break;
swap=divide[i];
for(int k=n-n/2-1+i;k>j;k--)
{
count++;
Data[k+1]=Data[k];
}
Data[k+1]=swap;
if(i!=k+1)
count+=2;
}
//输出结果
for(i=0;i<n;i++)
cout<<Data[i]<<' ';
cout<<endl;
return count;
}
//堆排序
void Exchange(int & number1,int & number2);
void Show(int Data[],int Number)
{
int line=0,Pow=0;
int space=(int)(log10(Number)/log10(2))+1;
for(int i=0;i<Number;i++)
{
if(i>=Pow)
{
if(i)
printf("\n");
for(int j=0;j<(int)(pow(2,space))-2;j++)
printf(" ");
if(line)
line*=2;
else
line=1;
Pow=Pow+line;
space--;
}
else
for(int j=0;j<(int)(pow(2,space+1)-2)*2;j++)
printf(" ");
printf("%4d",Data[i]);
}
cout<<endl;
}
int Fen(int Data[], int Number, int Position)
{
int count = 0;
if(Position >= Number)
return 0;
if(Position*2+1 >= Number)
return 0;
if(Data[Position] >= Data[Position*2+1])
{
if(Position*2+2 >= Number )
return 0;
if(Data[Position] >= Data[Position*2+2])
return 0;
Exchange(Data[Position],Data[Position*2+2]);
count+=3;
count+=Fen(Data,Number,Position*2+2);
return count;
}
if(Position*2+2 >= Number)
{
Exchange(Data[Position],Data[Position*2+1]);
count+=3;
count+=Fen(Data,Number,Position*2+1);
return count;
}
if(Data[Position]>=Data[Position*2+2])
{
Exchange(Data[Position],Data[Position*2+1]);
count+=3;
count+=Fen(Data,Number,Position*2+1);
return count;
}
if(Data[Position*2+1]>=Data[Position*2+2])
{
Exchange(Data[Position],Data[Position*2+1]);
count+=Fen(Data,Number,Position*2+1);
count+=3;
}
else
{
Exchange(Data[Position],Data[Position*2+2]);
count+=Fen(Data,Number,Position*2+2);
count+=3;
}
return count;
}
int FenPei(int Data[],int Number,int Position)
{
int count=0;
if(Position >= Number)
return 0;
if(Position*2+1 >= Number)
return 0;
count += FenPei(Data, Number, Position*2+1);
count += FenPei(Data, Number, Position*2+2);
if(Data[Position] >= Data[Position*2+1])
{
if(Position*2+2 >= Number)
return count;
if(Data[Position]>=Data[Position*2+2])
return count;
Exchange(Data[Position],Data[Position*2+2]);
count+=3;
count+=Fen(Data,Number,Position*2+2);
return count;
}
if(Position*2+2 >= Number)
{
Exchange(Data[Position],Data[Position*2+1]);
count+=3;
count+=Fen(Data,Number,Position*2+1);
return count;
}
if(Data[Position] > Data[Position*2+2])
{
Exchange(Data[Position],Data[Position*2+1]);
count+=3;
count+=Fen(Data,Number,Position*2+1);
return count;
}
if(Data[Position*2+1] >= Data[Position*2+2])
{
Exchange(Data[Position],Data[Position*2+1]);
count+=Fen(Data,Number,Position*2+1);
count+=3;
}
else
{
Exchange(Data[Position],Data[Position*2+2]);
count+=Fen(Data,Number,Position*2+2);
count+=3;
}
return count;
}
int Assign(int Data[], int Number)
{
int count=0;
count+=FenPei(Data,Number,0);
cout<<"\n树的形式显示："<<endl;
Show(Data,Number);
cout<<"数据的顺序：";
for(int j=0;j<Number;j++)
cout<<Data[j]<<' ';
cout<<endl;
for(int i=Number-1; i>0; i--)
{
Exchange(Data[0],Data[i]);
count+=3;
count+=Fen(Data,i,0);
cout<<"\n树的形式显示："<<endl;
Show(Data,i);
cout<<"数据的顺序：";
for(j=0;j<Number;j++)
cout<<Data[j]<<' ';
cout<<endl;
}
return count;
}
//希尔排序shell
int ShellSort(T a[], int N,int count)
{
count = 0;
for (int gap = N/2; gap; gap = gap/2)
for (int i = gap; i < N; i++)
{
T temp = a[i];
for (int j = i; j >= gap&& temp < a[j - gap]; j -= gap)
{
a[j] = a[j - gap];
count++;
}
a[j] = temp;
}
return count;
}
void main()
{
char *pstr1[]={" 算法课设研究 功能演示平台 ",//0
"*┏━━━━━━━━━━━━━━━━━━━━┓",//1
"*┃ 程序信息 ┃",//2
"*┠─────┬──────────────┨",//3
"*┃设计目的：│ 学习几种排序的算法 ┃",//4
"*┠─────┼──────────────┨",//5
"*┃程序功能：│ 几种排序算法的比较 ┃",//6
"*┠─────┼──────────────┨",//7
"*┃指导教师：│ 王问燕老师 ┃",//8
"*┠─────┼──────────────┨",//9
"*┃程序设计：│ 陈晓庆 ┃",//10
"*┠─────┼──────────────┨",//11
"*┃设计日期：│ 2008年2月26 日 ┃",//12
"*┠─────┴──────────────┨",//13
"*┃湖北汽车工业学院电系2008年算法课程设计 ┃",//14
"*┗━━━━━━━━━━━━━━━━━━━━┛"};//15
srand(time(0));
int count=0,number;
char ch;
CShow show;
show.SetType(pstr1,16,CShow::SH_LTORLINE,10);
while(1)
{
system("cls");
count=0;
show.Show();
cout<<"准备随机产生几个数据进行测试："<<endl;
cin>>number;
int * data=new int[number];
int * data1=new int[number];
int * data2=new int[number];
int * data3=new int[number];
for(int i=0;i<number;i++)
{
data[i]=rand()%1000;
data1[i]=data[i];
data2[i]=data[i];
data3[i]=data[i];
}
cout<<number<<"个随机数据是："<<endl;
for(i=0;i<number;i++)
cout<<data[i]<<' ';
cout<<endl;
cout<<"快速排序的过程显示："<<endl;
count=QuickSort(data,number);
cout<<"快速排序的结果："<<endl;
for(i=0;i<number;i++)
cout<<data[i]<<' ';
cout<<endl<<"快速排序移动数据的次数是："<<count/3<<"次"<<endl<<endl<<endl;
count=0;
cout<<number<<"个随机数据是："<<endl;
for(i=0;i<number;i++)
{
data[i]=data1[i];
cout<<data[i]<<' ';
}
cout<<endl;
cout<<"归并排序的过程显示："<<endl;
count=MergeSort(data,number);
cout<<"归并排序的结果："<<endl;
for(i=0;i<number;i++)
cout<<data[i]<<' ';
cout<<endl<<"归并排序移动数据的次数是："<<count/3<<"次"<<endl<<endl<<endl;
count=0;
cout<<number<<"个随机数据是："<<endl;
for(i=0;i<number;i++)
{
data[i]=data1[i];
cout<<data[i]<<' ';
}
cout<<endl;
int Data[210];int Number;
cout<<"堆排序的过程显示："<<endl;
count=Assign(data2,number);
cout<<"堆排序的结果："<<endl;
for(i=0;i<number;i++)
cout<<data2[i]<<' ';
cout<<endl<<"堆排序移动数据的次数是："<<count/3<<"次"<<endl;
int line=0,Pow=0;
int space=(int)(log10(Number)/log10(2))+1;
for(int k=0;k<Number;k++)
{
if(k>=Pow)
{
if(k)
printf("\n");
for(int j=0;j<(int)(pow(2,space))-2;j++)
printf(" ");
if(line)
line*=2;
else
line=1;
Pow=Pow+line;
space--;
}
else
for(int j=0;j<(int)(pow(2,space+1)-2)*2;j++)
printf(" ");
printf("%4d",Data[i]);
}
cout<<endl;
cout<<"归并排序的过程显示："<<endl;
count=0;
cout<<number<<"个随机数据是："<<endl;
for(i=0;i<number;i++)
cout<<data3[i]<<' ';
cout<<endl;
cout<<"希尔排序的结果是："<<endl;
count=ShellSort(data3,number,count);
for(i=0;i<number;i++)
cout<<data3[i]<<' ';
cout<<endl<<"排序的结果次数："<<count;
delete [] data;
delete [] data1;
delete [] data2;
delete [] data3;
cout<<"要继续测试吗?(Y/y)"<<endl;
cin>>ch;
if(!(ch=='Y'||ch=='y'))
break;
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -