排序综合

发布网友发布时间：2022-05-06 10:07

共1个回答

热心网友时间：2022-06-29 18:07

//这是我的
#include<fstream>
#include<iostream>
#include<cstdlib>//常用函数
#include<windows.h>
#include<time.h>
#include<iomanip>//格式化输出
using namespace std;
int compare[7],change[7],move[7]; //compare数组是比较次数，change数组是交换次数，move数组是移动次数
class SortableSList
{
public:
SortableSList();
void Reload(); //初始数据函数
void Save_File(); //保存信息
void InsertSort(); //直接插入排序
void SelectSort(); //简单选择排序
void BubbleSort(); //冒泡排序
void QuickSort(); //快速排序
void ShellSort(); //希尔排序
void HeapSort(); //堆排序
void MergeSort(); //两路合并排序
void QuickSort(int left,int right);
void PrintBeforeSort();
void PrintAfterSort();
private:
int Partition(int left,int right);
void InsSort(int h);
void Merge(int left,int mid,int right);
void Min(int i);
int *l;
int n;
int *randarray;
};
SortableSList::SortableSList()
{
cout<<" | 请你输入要排序的数字个数 n : ";
cin>>n;//输入要生成随机数的个数
cout<<" | |"<<endl;
cout<<" |----------------------------------------------------------------------------|"<<endl;
cout<<" | |"<<endl;
cout<<" | 请稍等...... |"<<endl;
l=new int[n];
randarray=new int[n];
for(int i=0;i<n;i++) //随机产生1~10000的数字
l[i]=randarray[i]=rand()%10000;
}

void SortableSList::Reload() //初始数据函数
{
int i;
for(i=0;i<n;i++)
l[i]=randarray[i];

}
void SortableSList::Save_File() //保存信息
{
int i;
ofstream ofile("排序.txt");//文件输出流
for(i=1;i<=n;i++)
ofile<<l[i]<<" ";//读取文件
ofile.close();
ifstream infile("排序.txt");//输入文件对操作
for(i=1;i<=n;i++)
infile>>l[i];
infile.close();
}
//~~~~~~~~~~~~~~~直接插入排序~~~~~~~~~~~~~~~~~~~
void SortableSList::InsertSort()
{
int i,j;
for(i=1;i<n;i++){
int x=l[i];
move[0]++;
for(j=i-1;j>=0&&x<l[j];j--)
{
compare[0]++;
l[j+1]=l[j],change[0]++;
move[0]++;
}
compare[0]++;
l[j+1]=x;
}
}
//~~~~~~~~~~~~~~~简单选择排序~~~~~~~~~~~~~~~~~~~~~
void Swap(int&a,int&b)
{
int e=a;a=b;b=e;
}

void SortableSList::SelectSort()
{
int s;
for(int i=0;i<n-1;i++)
{
s=i;
compare[1]++;
for(int j=i+1;j<n;j++)
if(l[j]<l[s]) s=j;
Swap(l[i],l[s]),move[1]=move[1]+3,change[1]++;
}
}
//~~~~~~~~~~~~~~~快速排序~~~~~~~~~~~~~~~~~~~~~~~~~
int SortableSList::Partition(int left,int right)
{
int i=left,j=right+1;
do{
do
{i++; compare[3]++;}while(l[i]<l[left]);
do
{j--; compare[3]++;}while(l[j]>l[left]);
if(i<j) Swap(l[i],l[j]),change[3]++;
}while(i<j);
Swap(l[left],l[j]),move[3]=move[3]+3,change[3]++;
return j;
}
void SortableSList::QuickSort(int left,int right)
{
if(left<right)
{
int j=Partition(left,right);
QuickSort(left,j-1);
QuickSort(j+1,right);
}
}

void SortableSList::QuickSort()
{

QuickSort(0,n-1);

}
//******************希尔排序**********************
void SortableSList::InsSort(int h)
{

int i,j;
int x;
for(i=h;i<n;i+=h){
x=l[i];
move[4]++;
compare[4]++;
change[4]++;
for(j=i-h;j>=0 && x<l[j];j-=h)
{
compare[4]++;
l[j+h]=l[j];
change[4]++;
move[4]++;
}
l[j+h]=x;
move[4]++;
}
}

void SortableSList::ShellSort()
{

int incr=n,i;
do{
incr=incr/3+1;
for(i=0;i<incr;i++) InsSort(incr);
}while(incr>1);
}
//~~~~~~~~~~~~~~~~~~~冒泡排序~~~~~~~~~~~~~~~~~~~~
void SortableSList::BubbleSort()
{

int i=n-1,k=1,j,last;
while(i>0){
last=0;
for(j=0;j<i;j++)
{
compare[2]++;
if(l[j+1]<l[j])
{
Swap(l[j],l[j+1]);
last=j;
}
move[2]=move[2]+3; //2指各个排序算法的标号，3指移动次数
}
change[2]++;
i=last;
}
}
//~~~~~~~~~~~~~~~~~~~堆排序~~~~~~~~~~~~~~~~~~
void SortableSList::Min(int i){
int m = i;
int s = i<<1;
int t = (i<<1)+1;
if(t>=n){
compare[5]++;
return ;
}
if(l[s]<l[m]){
m = s;
compare[5]++;
change[5]++;
}
if(l[t]<l[m]){
m = t;
compare[5]++;
change[5]++;
}
if(m!=i)
{
move[5]++;
swap(l[m],l[i]);
Min(m);
}
}
void SortableSList::HeapSort(){
for(int i=(n>>1)-1;i>=0;i--){
Min(i);
}
}
//~~~~~~~~~~~~~~~~~~~两路合并排序~~~~~~~~~~~~~~~~~~
void SortableSList::MergeSort()
{

int left,right,mid,size=1; //变量size是子序列的大小,初值为1
while(size<n)
{
left=0;
while(left+size<n)
{
mid=left+size-1;
if(mid+size>n-1)right=n-1;
else right=mid+size;
Merge(left,mid,right);
left=right+1;
}
size*=2; //每趟排序结束时size都乘2
}
}
void SortableSList::Merge (int left,int mid,int right)
{
int*temp=new int[right-left+1];
int i=left,j=mid+1,k=0;
while((i<=mid)&&(j<=right)){
compare[6]++;
if(l[i]<=l[j]) temp[k++]=l[i++],change[6]++;
else temp[k++]=l[j++],move[6]++,change[6]++;
}
while(i<=mid) temp[k++]=l[i++],move[6]++,change[6]++; //将2个子序列 (l[left],...l[mid])和(l[mid+1],...l[right])
//合并为一个有序子序列
while(j<=right) temp[k++]=l[j++],move[6]++,change[6]++;
for(i=0,k=left;k<=right;) l[k++]=temp[i++],move[6]++,change[6]++;
}
//~~~~~~~~~~~~~~~~~~~排序输出~~~~~~~~~~~~~~~~~~
void SortableSList::PrintBeforeSort(){
cout<<"排序前的数组:\n";
for(int i=0;i<n;i++){
cout<<randarray[i]<<" ";
if((i+1)%10==0)cout<<endl;
}
}
void SortableSList::PrintAfterSort(){
cout<<"排序后的数组:\n";
for(int i=0;i<n;i++){
cout<<l[i]<<" ";
if((i+1)%10==0)cout<<endl;
}
}
int main()
{
int i,j;
for(i=0;i<7;i++)//六种排序的循环
{ compare[i]=change[i]=move[i]=0;}
long int spendtime[7];
int range[7];//排名
long int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14;//起始时间，也就是当前时间
int select;
bool a=true;
cout<<" *----------------------------------------------------------------------------*"<<endl;
cout<<" | 各种内排序算法的性能比较 |"<<endl;
cout<<" |----------------------------------------------------------------------------|"<<endl;
cout<<" | |"<<endl;
cout<<" | 1-生成目标列表比较各个内排序算法 |"<<endl;
cout<<" | |"<<endl;
//cout<<" | 3-打印排序前和排序后的数组 |"<<endl;
//cout<<" | |"<<endl;
cout<<" | 2-退出系统 |"<<endl;
cout<<" | |"<<endl;
cout<<" |----------------------------------------------------------------------------|"<<endl;
do{
cout<<" | |"<<endl;
cout<<" | 请输入你要选择的操作: ";
cin>>select;
cout<<" | |"<<endl;
if(select==1){
SortableSList d;
d.Save_File();
t1=GetTickCount();
d.InsertSort ();
t2=GetTickCount();
d.Reload();
t3=GetTickCount();
d.SelectSort ();
t4=GetTickCount();
d.Reload();
t5=GetTickCount();
d.BubbleSort ();
t6=GetTickCount();
d.Reload();//恢复到初始数据函数
t7=GetTickCount();
d.QuickSort ();
t8=GetTickCount();
d.Reload();
t9=GetTickCount();
d.ShellSort ();
t10=GetTickCount();
d.Reload();
t11=GetTickCount();
d.HeapSort();
t12=GetTickCount();
d.Reload();
t13=GetTickCount();
d.MergeSort();
t14=GetTickCount();
spendtime[0]=t2-t1;
spendtime[1]=t4-t3;
spendtime[2]=t6-t5;
spendtime[3]=t8-t7;
spendtime[4]=t10-t9;
spendtime[5]=t12-t11;
spendtime[6]=t14-t13;
for(i=0;i<7;i++)//根据花费时间进行排名
{
int t=1;
for(j=0;j<7;j++)

{
if(i!=j)
if(spendtime[i]>spendtime[j]) t++;
}
range[i]=t;
}
cout<<" | |"<<endl;
cout<<" | 总共用时: 约为"<<setw(5)<<spendtime[0]+spendtime[1]+spendtime[2]+spendtime[3]+spendtime[4]<<"毫秒 |"<<endl;
cout<<" |----------------------------------------------------------------------------|"<<endl;
cout<<" | --- 结果如下 --- |"<<endl;
cout<<" |----------------------------------------------------------------------------|"<<endl;
cout<<" |排序的名称"<<setw(3)<<"| 比较次数"<<setw(3)<<"|交换的次数"<<setw(3)<<"|移动的次数"<<setw(3)<<"| 时间(ms) "<<"| 时间排名 "<<setw(3)<<"| 时间复杂度|"<<endl;
cout<<" |----------+---------+----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 插入排序 |"<<setw(8)<<compare[0]<<" |"<<setw(8)<<change[0]<<" |"<<setw(9)<<move[0]<<" |"<<setw(8)<<spendtime[0]<<" |"<<setw(8)<<range[0]<<" |"<<setw(11)<<" n*n |"<<endl;
cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 选择排序 |"<<setw(8)<<compare[1]<<" |"<<setw(8)<<change[1]<<" |"<<setw(9)<<move[1]<<" |"<<setw(8)<<spendtime[1]<<" |"<<setw(8)<<range[1]<<" |"<<setw(11)<<" n*n |"<<endl;
cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 冒泡排序 |"<<setw(8)<<compare[2]<<" |"<<setw(8)<<change[2]<<" |"<<setw(9)<<move[2]<<" |"<<setw(8)<<spendtime[2]<<" |"<<setw(8)<<range[2]<<" |"<<setw(11)<<" n*n |"<<endl;
cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 快速排序 |"<<setw(8)<<compare[3]<<" |"<<setw(8)<<change[3]<<" |"<<setw(9)<<move[3]<<" |"<<setw(8)<<spendtime[3]<<" |"<<setw(8)<<range[3]<<" |"<<setw(11)<<" n*log2n |"<<endl;
cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 希尔排序 |"<<setw(8)<<compare[4]<<" |"<<setw(8)<<change[4]<<" |"<<setw(9)<<move[4]<<" |"<<setw(8)<<spendtime[4]<<" |"<<setw(8)<<range[4]<<" |"<<setw(11)<<" n*log2n |"<<endl;
cout<<" |----------+---------|----------+----------+----------+----------+-----------|"<<endl;
cout<<" | 堆排序 |"<<setw(8)<<compare[5]<<" |"<<setw(8)<<change[5]<<" |"<<setw(9)<<move[5]<<" |"<<setw(8)<<spendtime[5]<<" |"<<setw(8)<<range[5]<<" |"<<setw(11)<<" n*log2n |"<<endl;
cout<<" *----------------------------------------------------------------------------*"<<endl;
cout<<" | 合并排序 |"<<setw(8)<<compare[6]<<" |"<<setw(8)<<change[6]<<" |"<<setw(9)<<move[6]<<" |"<<setw(8)<<spendtime[6]<<" |"<<setw(8)<<range[6]<<" |"<<setw(11)<<" n*log2n |"<<endl;
cout<<" *----------------------------------------------------------------------------*"<<endl;
a=true;
cout<<"\n是否打印排序前和排序后的队列（选1 打印或选2 返回）\n";
int sel;
cin>>sel;
if(sel==1){
d.PrintBeforeSort();
d.PrintAfterSort();
}
else if(sel==2){
continue;
}
}
else if(select==2)
{
cout<<" *----------------------------------------------------------------------------*"<<endl;
cout<<" | --- 程序结束 --- |"<<endl;
cout<<" *----------------------------------------------------------------------------*"<<endl;
a=false;
}
else
{
cout<<" | 你的输入有错误，请重新输入！ |"<<endl;
cout<<" | |"<<endl;
a=true;
}
}while(a==true);
return 0;
}