C++中十种内部排序算法的比较分析
宰父正真
本文向大家介绍C++中十种内部排序算法的比较分析，包括了C++中十种内部排序算法的比较分析的使用技巧和注意事项，需要的朋友参考一下
C++中十种内部排序算法的比较分析
#include<iostream>
#include<ctime>
#include<fstream>
using namespace std;
#define MAXSIZE 1000 //可排序表的最大长度
#define SORTNUM 10 //测试10中排序方法
#define max 100 //基数排序时数据的最大位数不超过百位；
typedef struct node {
int data3;
int next;
} node;
typedef int DataType[MAXSIZE+2];
DataType data;
DataType data2;
DataType R1;
int size;//可排序表的长度
int head;
int fr[10];
int re[10];
long compCount;//统计比较次数
long shiftCount;//统计移动次数
void BeforeSort()//对比较次数和移动次数清零
{
compCount=0;
shiftCount=0;
}
bool Less(int i,int j)//若表中第i个元素小于第j个元素，则返回True，否则返回False
{
compCount++;
return data[i]<data[j];
}
void Swap(int i,int j)//交换表中第i个和第j个元素
{
int a;
a=data[i];
data[i]=data[j];
data[j]=a;
shiftCount=shiftCount+3;
}
void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i]
{
R[i]=R2[j];
shiftCount++;
}
void CopyData(DataType list1,DataType list2)
{
int i;
for(i=1;i<=size;i++) list2[i]=list1[i];
}
void InverseOrder()//将可排序表置为逆序
{
int i,j;
for(i=1,j=size;i<=size/2;i++,j--)
{
int a;
a=data[i];
data[i]=data[j];
data[j]=a;
}
CopyData(data,data2);
}
void RandomizeList()//由系统随机一组数
{
int i;
srand(time(0));
for(i=1;i<=size;i++)
data[i]=rand()%(size+1);
CopyData(data,data2);
ofstream out_stream;
out_stream.open("input.txt",ios::app);
if(out_stream.fail())
{
cout<<"input file opening failed.\n";
exit(1);
}
for(i=1;i<=size;i++) out_stream<<data[i]<<" ";
out_stream<<"\n";
out_stream.close();
}
void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表
{
CopyData(data2,data);
}
void output()//输出函数
{
ofstream out_stream;
cout<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
{
cout<<"Output file opening failed.\n";
exit(1);
}
out_stream<<"\t"<<compCount<<"\t\t"<<shiftCount<<"\n";
out_stream.close();
}
void BubbleSort()//冒泡排序
{
BeforeSort();
int swapped,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();
}
void InsertSort() //插入排序
{
BeforeSort();
int i,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();
}
void SelectSort()//选择排序
{
BeforeSort();
int i,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();
}
int Partition(int low,int high)
{
int pivotkey;
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);
return low;
}
void QSort(int low,int high)//QuickSort的辅助函数
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
void QuickSort()//快速排序
{
BeforeSort();
QSort(1,size);
output();
}
void ShellSort()//希尔排序
{
BeforeSort();
int i,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();
}
void Sift(int left,int right)//堆排序的调堆函数
{
int i,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);
}
void HeapSort()//堆排序
{
int left,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();
}
void BInsertSort()//折半插入排序
{
BeforeSort();
int i,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;
else low=m+1;
}
for(j=i-1;j>=high+1;j--) Shift(data,data,j+1,j);
Shift(data,data,high+1,0);
}
output();
}
void Binsort()//2-路插入排序
{
BeforeSort();
int i,k,j;
int first,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();
}
void Merge(int low,int m,int high)
{
int i=low,j=m+1,p=1;
while(i<=m&&j<=high)
{
if(Less(i,j)) Shift(R1,data,p++,i++);
else Shift(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);
}
void MSort(int low, int high)
{
int mid;
if (low<high){
mid=(low+high)/2;
MSort(low, mid);
MSort(mid+1,high);
Merge(low, mid, high);
}
}
void MergeSort()//归并排序
{
BeforeSort();
MSort(1,size);
output();
}
void Distribute(node *a, int w)
{
int i;
for (i=0; i<10; i++) fr[i] = -1;
for (i=head; i!=-1; i=a[i].next)
{
int x = 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;
}
}
}
void Collect(node *a)
{
int i, 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;
}
void RadixSort()//基数排序算法。
{
BeforeSort();
ofstream out_stream;
node* a;
a=new node[size];
int i,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();
}
void Initialization()//系统初始化
{
system("cls");//清屏
cout<<"***************************************************************************\n"
<<"***************** 《内部排序算法的比较》 ********************************\n"
<<"***************************************************************************\n"
<<"************************ *主菜单* ***************************************\n"
<<"******* 1.由系统随机产生待排序表 ****************************************\n"
<<"******* 2.手动输入待排序表 **********************************************\n"
<<"******* 3.返回主菜单 ****************************************************\n"
<<"******* 4.退出程序 ******************************************************\n"
<<"***************************************************************************\n"
<<"请输入要执行的步骤：";
}
void Interpret(int cmd)//调用各个算法
{
int i,j,m;
ofstream out_stream;
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
{
cout<<"Output file opening failed.\n";
exit(1);
}
switch(cmd)
{
case 1:
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;
case 2:
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;
case 3:
Initialization();
break;
}
}
void main()
{
Initialization();
int cmd;
do{
cin>>cmd;
Interpret(cmd);
}while(cmd!=4);
}
以上就是本文所述的全部内容了，希望能够对大家熟悉掌握这十种排序算法有所帮助。
类似资料：
-
本文向大家介绍C#排序算法的比较分析，包括了C#排序算法的比较分析的使用技巧和注意事项，需要的朋友参考一下 本文实例分析了C#的各种排序算法。分享给大家供大家参考。具体分析如下： 首先通过图表比较不同排序算法的时间复杂度和稳定性。 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入排序 O(n2) O(n2) O(n) O(1) 是 冒泡排序 O(n2) O(n2) O(n)
-
本文向大家介绍基于C++实现的各种内部排序算法汇总，包括了基于C++实现的各种内部排序算法汇总的使用技巧和注意事项，需要的朋友参考一下 提起排序算法相信大家都不陌生，或许很多人已经把它们记得滚瓜烂熟，甚至随时可以写出来。是的，这些都是最基本的算法。这里就把各种内部排序算法总结归纳了一下，包括插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆
-
排序算法有不少，当然，一般的语言中都提供某个排序函数，比如Python中，对list进行排序，可以使用sorted（或者list.sort()），关于这方面的使用，在我的github代码库algorithm中有几个举例，有兴趣的看官可以去那里看看（顺便告知，我在Github中的账号是qiwsir，欢迎follow me）。但是，在某些情况下，语言中提供的排序方法或许不适合，必须选择某种排序算法。
-
本文向大家介绍C++线性时间的排序算法分析，包括了C++线性时间的排序算法分析的使用技巧和注意事项，需要的朋友参考一下 前面的文章已经介绍了几种排序算法，如插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序（可以参考前一篇文章：各种内部排序算法的实现）等，这些排序算法都有一个共同的特点，就是基于比较。 本文将介绍三种非
-
排序是数据结构体系中最重要的内容之一，这一块必须要非常熟练的掌握，应该做到可以立马写出每个排序的代码，有多种实现方法的必须多种都能很快写出来，当然对各个排序的性能的了解也是基础且重要的。我们先对排序这一块进行一个整体的把握。
-
本文向大家介绍C#排序算法之堆排序，包括了C#排序算法之堆排序的使用技巧和注意事项，需要的朋友参考一下 本文实例为大家分享了C#实现堆排序的具体代码，供大家参考，具体内容如下 代码： 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持呐喊教程。