C++中十種內(nèi)部排序算法的比較分析
更新時間：2015年03月29日 11:04:53 投稿：hebedich
本文給大家分享的是個人寫的一段對C++中十種內(nèi)部排序算法的比較分析的代碼，主要在于測試10種排序方法的性能，給大家參考下吧。
C++中十種內(nèi)部排序算法的比較分析
#include<iostream>
#include<ctime>
#include<fstream>
using namespace std;
#define MAXSIZE 1000 //可排序表的最大長度
#define SORTNUM 10 //測試10中排序方法
#define max 100 //基數(shù)排序時數(shù)據(jù)的最大位數(shù)不超過百位；
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;//統(tǒng)計比較次數(shù)
long shiftCount;//統(tǒng)計移動次數(shù)
void BeforeSort()//對比較次數(shù)和移動次數(shù)清零
{
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()//由系統(tǒng)隨機一組數(shù)
{
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()//恢復(fù)最后一次用RandomizeList隨機打亂的可排序表
{
CopyData(data2,data);
}
void output()//輸出函數(shù)
{
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的輔助函數(shù)
{
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)//堆排序的調(diào)堆函數(shù)
{
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()//基數(shù)排序算法。
{
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()//系統(tǒng)初始化
{
system("cls");//清屏
cout<<"***************************************************************************\n"
<<"***************** 《內(nèi)部排序算法的比較》 ********************************\n"
<<"***************************************************************************\n"
<<"************************ *主菜單* ***************************************\n"
<<"******* 1.由系統(tǒng)隨機產(chǎn)生待排序表 ****************************************\n"
<<"******* 2.手動輸入待排序表 **********************************************\n"
<<"******* 3.返回主菜單 ****************************************************\n"
<<"******* 4.退出程序 ******************************************************\n"
<<"***************************************************************************\n"
<<"請輸入要執(zhí)行的步驟：";
}
void Interpret(int cmd)//調(diào)用各個算法
{
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<<"由系統(tǒng)隨機產(chǎn)生待排序表的各個算法的比較次數(shù)和移動次數(shù)如下:\n";
out_stream<<"\tcompCount\tshiftCount\n";
out_stream.close();
cout<<"請輸入待排序表的長度:";
cin>>size;
cout<<"由系統(tǒng)隨機產(chǎn)生待排序表的各個算法的比較次數(shù)和移動次數(shù)如下:\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<<"個數(shù)據(jù):\n";
for(i=1;i<=size;i++) cin>>data[i];
CopyData(data,data2);
out_stream<<"手動輸入待排序表的各個算法的比較次數(shù)和移動次數(shù)如下:\n";
out_stream<<"\tcompCount\tshiftCount\n";
out_stream.close();
cout<<"手動輸入待排序表的各個算法的比較次數(shù)和移動次數(shù)如下:\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);
}
以上就是本文所述的全部內(nèi)容了，希望能夠?qū)Υ蠹沂煜ふ莆者@十種排序算法有所幫助。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)掃雷游戲，控制臺版的掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
在本篇文章里小編給大家整理的是關(guān)于c語言動態(tài)內(nèi)存分配知識點及實例，需要的朋友們可以學(xué)習(xí)下。2020-03-03
添加結(jié)點其實很容易，我們只需要找到結(jié)點所行對應(yīng)的位置就可以了，而且沒有要求是平衡的二叉搜索樹，因此每次添加結(jié)點都是在葉子結(jié)點上操作，不需要修改二叉搜索樹整體的結(jié)構(gòu)2013-09-09
Linux搭建C++開發(fā)調(diào)試環(huán)境的方法步驟
這篇文章主要介紹了Linux搭建C++開發(fā)調(diào)試環(huán)境的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
核密度估計是用于估計隨機變量概率密度函數(shù)的一種非參數(shù)方法。核密度圖不失為一種用來觀察連續(xù)型變量分布的有效方法。本文將用Matlab實現(xiàn)帶豎線散點的核密度圖的繪制，感興趣的可以了解一下2022-08-08
C++實現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細(xì)介紹了如何基于Qt實現(xiàn)一個圖片對比選擇瀏覽器,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
所謂缺省參數(shù)，顧名思義，就是在聲明函數(shù)的某個參數(shù)的時候為之指定一個默認(rèn)值，在調(diào)用該函數(shù)的時候如果采用該默認(rèn)值，你就無須指定該參數(shù)。缺省參數(shù)使用主要規(guī)則：調(diào)用時你只能從最后一個參數(shù)開始進行省略，換句話說，如果你要省略一個參數(shù)，你必須省略它后面所有的參數(shù)2022-05-05
C語言中結(jié)構(gòu)體偏移及結(jié)構(gòu)體成員變量訪問方式的問題討論
這篇文章主要介紹了C語言中結(jié)構(gòu)體偏移及結(jié)構(gòu)體成員變量訪問方式的問題討論,幫助大家理解struct的成員變量偏移,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了C語言計算1/1+1/2+1/3+…+1/n的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11