C++中十种内部排序算法的比较分析
C++中十种内部排序算法的比较分析
#include<iostream>
#include<ctime>
#include<fstream>
usingnamespacestd;
#defineMAXSIZE1000//可排序表的最大长度
#defineSORTNUM10//测试10中排序方法
#definemax100//基数排序时数据的最大位数不超过百位；
typedefstructnode{
intdata3;
intnext;
}node;
typedefintDataType[MAXSIZE+2];
DataTypedata;
DataTypedata2;
DataTypeR1;
intsize;//可排序表的长度
inthead;
intfr[10];
intre[10];
longcompCount;//统计比较次数
longshiftCount;//统计移动次数
voidBeforeSort()//对比较次数和移动次数清零
{
compCount=0;
shiftCount=0;
}
boolLess(inti,intj)//若表中第i个元素小于第j个元素，则返回True，否则返回False
{
compCount++;
returndata[i]<data[j];
}
voidSwap(inti,intj)//交换表中第i个和第j个元素
{
inta;
a=data[i];
data[i]=data[j];
data[j]=a;
shiftCount=shiftCount+3;
}
voidShift(DataType&R,DataType&R2,inti,intj)//将R2[j]赋给R[i]
{
R[i]=R2[j];
shiftCount++;
}
voidCopyData(DataTypelist1,DataTypelist2)
{
inti;
for(i=1;i<=size;i++)list2[i]=list1[i];
}
voidInverseOrder()//将可排序表置为逆序
{
inti,j;
for(i=1,j=size;i<=size/2;i++,j--)
{
inta;
a=data[i];
data[i]=data[j];
data[j]=a;
}
CopyData(data,data2);
}
voidRandomizeList()//由系统随机一组数
{
inti;
srand(time(0));
for(i=1;i<=size;i++)
data[i]=rand()%(size+1);
CopyData(data,data2);
ofstreamout_stream;
out_stream.open("input.txt",ios::app);
if(out_stream.fail())
{
cout<<"inputfileopeningfailed.\n";
exit(1);
}
for(i=1;i<=size;i++)out_stream<<data[i]<<"";
out_stream<<"\n";
out_stream.close();
}
voidRecallList()//恢复最后一次用RandomizeList随机打乱的可排序表
{
CopyData(data2,data);
}
voidoutput()//输出函数
{
ofstreamout_stream;
cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
{
cout<<"Outputfileopeningfailed.\n";
exit(1);
}
out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
out_stream.close();
}
voidBubbleSort()//冒泡排序
{
BeforeSort();
intswapped,i,m;
m=size-1;
do{
swapped=0;
for(i=1;i<=m;i++)
{
if(Less(i+1,i))
{
Swap(i+1,i);
swapped=1;
}
}
m--;
}while(swapped);
output();
}
voidInsertSort()//插入排序
{
BeforeSort();
inti,j;
for(i=2;i<=size;i++)
{
Shift(data,data,0,i);
j=i-1;
while(Less(0,j))
{
Shift(data,data,j+1,j);
j--;
}
Shift(data,data,j+1,0);
}
output();
}
voidSelectSort()//选择排序
{
BeforeSort();
inti,j,min;
for(i=1;i<=size-1;i++)
{
min=i;
for(j=i+1;j<=size;j++)
if(Less(j,min))min=j;
if(i!=min)Swap(i,min);
}
output();
}
intPartition(intlow,inthigh)
{
intpivotkey;
Shift(data,data,0,low);
pivotkey=data[low];
while(low<high)
{
compCount++;
while(low<high&&data[high]>=pivotkey){compCount++;--high;}
Shift(data,data,low,high);
compCount++;
while(low<high&&data[low]<=pivotkey){compCount++;++low;}
Shift(data,data,high,low);
}
Shift(data,data,low,0);
returnlow;
}
voidQSort(intlow,inthigh)//QuickSort的辅助函数
{
intpivotloc;
if(low<high)
{
pivotloc=Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
voidQuickSort()//快速排序
{
BeforeSort();
QSort(1,size);
output();
}
voidShellSort()//希尔排序
{
BeforeSort();
inti,j,h;
i=4;
h=1;
while(i<=size)
{
i=i*2;
h=2*h+1;
}
while(h!=0)
{
i=h;
while(i<=size)
{
j=i-h;
while(j>0&&Less(j+h,j))
{
Swap(j,j+h);
j=j-h;
}
i++;
}
h=(h-1)/2;
}
output();
}
voidSift(intleft,intright)//堆排序的调堆函数
{
inti,j,finished=0;
i=left;
j=2*i;
Shift(data,data,0,left);
Shift(data,data,MAXSIZE+1,left);
while(j<=right&&!finished)
{
if(j<right&&Less(j,j+1))j=j+1;
if(!Less(0,j))finished=1;
else
{
Shift(data,data,i,j);
i=j;
j=2*i;
}
}
Shift(data,data,i,MAXSIZE+1);
}
voidHeapSort()//堆排序
{
intleft,right;
BeforeSort();
for(left=size/2;left>=1;left--)Sift(left,size);
for(right=size;right>=2;right--)
{
Swap(1,right);
Sift(1,right-1);
}
output();
}
voidBInsertSort()//折半插入排序
{
BeforeSort();
inti,low,high,m,j;
for(i=2;i<=size;i++)
{
Shift(data,data,0,i);
low=1;
high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(Less(0,m))high=m-1;
elselow=m+1;
}
for(j=i-1;j>=high+1;j--)Shift(data,data,j+1,j);
Shift(data,data,high+1,0);
}
output();
}
voidBinsort()//2-路插入排序
{
BeforeSort();
inti,k,j;
intfirst,last;
first=last=1;
Shift(R1,data,1,1);
for(i=2;i<=size;i++)
{
compCount++;
if(data[i]>=R1[1])
{
compCount++;
j=last;
while(j>=1&&R1[j]>data[i])
{
Shift(R1,R1,j+1,j);
j--;
compCount++;
}
Shift(R1,data,j+1,i);
last++;
}
else
{
first--;
if(first==0)first=size;
j=first+1;
compCount++;
while(j<=size&&R1[j]<=data[i])
{
Shift(R1,R1,j-1,j);
j++;
compCount++;
}
Shift(R1,data,j-1,i);
}
}
k=1;
j=first;
while(k<=size)
{
Shift(data,R1,k,j);
k++;
j=(j+1)%(size+1);
if(j==0)j=j+1;
}
output();
}
voidMerge(intlow,intm,inthigh)
{
inti=low,j=m+1,p=1;
while(i<=m&&j<=high)
{
if(Less(i,j))Shift(R1,data,p++,i++);
elseShift(R1,data,p++,j++);
}
while(i<=m)
Shift(R1,data,p++,i++);
while(j<=high)
Shift(R1,data,p++,j++);
for(p=1,i=low;i<=high;p++,i++)
Shift(data,R1,i,p);
}
voidMSort(intlow,inthigh)
{
intmid;
if(low<high){
mid=(low+high)/2;
MSort(low,mid);
MSort(mid+1,high);
Merge(low,mid,high);
}
}
voidMergeSort()//归并排序
{
BeforeSort();
MSort(1,size);
output();
}
voidDistribute(node*a,intw)
{
inti;
for(i=0;i<10;i++)fr[i]=-1;
for(i=head;i!=-1;i=a[i].next)
{
intx=a[i].data3/w%10;
if(fr[x]==-1)
{
fr[x]=re[x]=i;
compCount++;
}
else
{
a[re[x]].next=i;
re[x]=i;
shiftCount++;
}
}
for(i=0;i<10;i++)
{
if(fr[i]!=-1)
{
a[re[i]].next=-1;
}
}
}
voidCollect(node*a)
{
inti,last;
last=-1;
for(i=0;i<10;i++)
{
if(fr[i]!=-1)
{
if(last==-1)
{
head=fr[i];
last=re[i];
}
else{
a[last].next=fr[i];
last=re[i];
shiftCount++;
}
}
}
a[last].next=-1;
}
voidRadixSort()//基数排序算法。
{
BeforeSort();
ofstreamout_stream;
node*a;
a=newnode[size];
inti,j=1;
for(i=0;i<size;i++){
a[i].data3=data[i+1];
a[i].next=i+1;
}
head=0;
a[size-1].next=-1;
for(i=1;i<=max;i*=10){
Distribute(a,i);
Collect(a);
}
cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
while(head!=-1)
{
data[j++]=a[head].data3;
head=a[head].next;
}
CopyData(data,data2);
cout<<"\n";
out_stream.open("output.txt",ios::app);
out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n\n";
out_stream.close();
}
voidInitialization()//系统初始化
{
system("cls");//清屏
cout<<"***************************************************************************\n"
<<"*****************《内部排序算法的比较》********************************\n"
<<"***************************************************************************\n"
<<"*************************主菜单****************************************\n"
<<"*******1.由系统随机产生待排序表****************************************\n"
<<"*******2.手动输入待排序表**********************************************\n"
<<"*******3.返回主菜单****************************************************\n"
<<"*******4.退出程序******************************************************\n"
<<"***************************************************************************\n"
<<"请输入要执行的步骤：";
}
voidInterpret(intcmd)//调用各个算法
{
inti,j,m;
ofstreamout_stream;
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
{
cout<<"Outputfileopeningfailed.\n";
exit(1);
}
switch(cmd)
{
case1:
out_stream<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream<<"\tcompCount\tshiftCount\n";
out_stream.close();
cout<<"请输入待排序表的长度:";
cin>>size;
cout<<"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
RandomizeList();
for(m=0;m<3;m++)
{
if(m==2)InverseOrder();
cout<<"\t";
for(i=1;i<=size;i++)cout<<data[i]<<"";
cout<<"\n";
cout<<"\tcompCount\tshiftCount\n";
for(j=0;j<SORTNUM;j++)
{
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0){cout<<"Bubbl:";out_stream<<"Bubbl:";out_stream.close();BubbleSort();}
if(j==1){cout<<"Tnser:";out_stream<<"Tnser:";out_stream.close();InsertSort();}
if(j==2){cout<<"Selec:";out_stream<<"Selec:";out_stream.close();SelectSort();}
if(j==3){cout<<"Quick:";out_stream<<"Quick:";out_stream.close();QuickSort();}
if(j==4){cout<<"Shell:";out_stream<<"Shell:";out_stream.close();ShellSort();}
if(j==5){cout<<"Heap:";out_stream<<"Heap:";out_stream.close();HeapSort();}
if(j==6){cout<<"BInse:";out_stream<<"BInse:";out_stream.close();BInsertSort();}
if(j==7){cout<<"Merge:";out_stream<<"Merge:";out_stream.close();MergeSort();}
if(j==8){cout<<"Bin:";out_stream<<"Bin:";out_stream.close();Binsort();}
if(j==9){cout<<"Radix:";out_stream<<"Radix:";out_stream.close();RadixSort();}
}}
//}
break;
case2:
cout<<"请输入待排序表的长度：";
cin>>size;
cout<<"请输入"<<size<<"个数据:\n";
for(i=1;i<=size;i++)cin>>data[i];
CopyData(data,data2);
out_stream<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream<<"\tcompCount\tshiftCount\n";
out_stream.close();
cout<<"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
cout<<"\tcompCount\tshiftCount\n";
for(j=0;j<SORTNUM;j++)
{
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0){cout<<"Bubbl:";out_stream<<"Bubbl:";out_stream.close();BubbleSort();}
if(j==1){cout<<"Tnser:";out_stream<<"Tnser:";out_stream.close();InsertSort();}
if(j==2){cout<<"Selec:";out_stream<<"Selec:";out_stream.close();SelectSort();}
if(j==3){cout<<"Quick:";out_stream<<"Quick:";out_stream.close();QuickSort();}
if(j==4){cout<<"Shell:";out_stream<<"Shell:";out_stream.close();ShellSort();}
if(j==5){cout<<"Heap:";out_stream<<"Heap:";out_stream.close();HeapSort();}
if(j==6){cout<<"BInse:";out_stream<<"BInse:";out_stream.close();BInsertSort();}
if(j==7){cout<<"Merge:";out_stream<<"Merge:";out_stream.close();MergeSort();}
if(j==8){cout<<"Bin:";out_stream<<"Bin:";out_stream.close();Binsort();}
if(j==9){cout<<"Radix:";out_stream<<"Radix:";out_stream.close();RadixSort();}
}
break;
case3:
Initialization();
break;
}
}
voidmain()
{
Initialization();
intcmd;
do{
cin>>cmd;
Interpret(cmd);
}while(cmd!=4);
}
以上就是本文所述的全部内容了，希望能够对大家熟悉掌握这十种排序算法有所帮助。