排序算法實(shí)驗(yàn)報(bào)告

排序算法實(shí)驗(yàn)報(bào)告（內(nèi)部排序算法比較）主要實(shí)驗(yàn)內(nèi)容：對各種內(nèi)部排序算法進(jìn)行比較要求：（1）任意輸入5組各50個(gè)數(shù)據(jù)；（2）對冒泡排序、直接插入排序、簡單選擇排序、快速排序、堆排序的關(guān)鍵字比較和交換次數(shù)進(jìn)行統(tǒng)計(jì)。源程序代碼：//主函數(shù)文件”sort.cpp”#include<iostream>#include<cstdlib>usingnamespacestd;#include"Sort.h"#defineNUMLEN50//要排序數(shù)組的元素個(gè)數(shù)/***********************main函數(shù)部分*******************************************/voidmain(){ Rec*createData(inti,int&n);//創(chuàng)建5組數(shù)據(jù)元素 voidDataHandle(Sort&data,Rec*r,intn);//處理每種排序的調(diào)用過程 voidShowData(inti,Rec*r,intn); //顯示創(chuàng)建好的未排序過的數(shù)組元素 intn;//記錄待排序數(shù)組元素的個(gè)數(shù) Rec*r;//用以儲存待排序的數(shù)組元素 Sortdata;//創(chuàng)建排序?qū)ο?通過對象調(diào)用排序函數(shù),完成對數(shù)據(jù)元素的排序 for(inti=0;i<5;i++) { r=createData(i,n); ShowData(i,r,n); DataHandle(data,r,n); }}/******************************************************************************//**************createData函數(shù)部分**********************************************//*功能:根據(jù)需要創(chuàng)建5組互不相同的數(shù)據(jù)元素*/Rec*createData(inti,int&n){ n=NUMLEN; intj; Rec*r=newRec[n+1]; r[0].key=0; switch(i+1) { case1://創(chuàng)建升序排序的1-50的數(shù)組 for(j=1;j<=n;j++) r[j].key=j; break; case2://創(chuàng)建降序排序的50-1的數(shù)組 for(j=1;j<=n;j++) r[j].key=n+1-j; break; case3://創(chuàng)建前半部分是升序排序的1-25的數(shù)組,后半部分降序排序的50-26的數(shù)組 for(j=1;j<=n/2;j++) r[j].key=j; if(n%2==0) for(j=1;j<=n/2;j++) r[j+n/2].key=n+1-j; else for(j=1;j<=n/2+1;j++) r[j+n/2].key=n+1-j; break; case4://創(chuàng)建一個(gè)全部元素都都為1的數(shù)組 for(j=1;j<=n;j++) r[j].key=3; break; case5://程序隨機(jī)的創(chuàng)建一個(gè)大小為n的范圍為1-1000之間的隨機(jī)數(shù)組 srand(333); for(j=1;j<=n;j++) r[j].key=rand()%1000+1; break; default:returnNULL; } returnr;}/***********************ShowData函數(shù)部分***************************************//*功能:顯示創(chuàng)建好的未排序的數(shù)組元素*/voidShowData(inti,Rec*r,intn){cout<<endl<<"********************************************************************************";cout<<"The"<<i+1<<"primaryarrayis:"<<endl;for(intj=1;j<=n;j++) cout<<r[j].key<<"";cout<<endl<<"********************************************************************************"<<endl;}/******************************************************************************//********************DataHandl函數(shù)部分*****************************************//*功能:處理每種排序的調(diào)用過程*/voidDataHandle(Sort&data,Rec*r,intn){ cout<<endl<<"Bubblesort"<<endl; data.CreateData(r,n); data.BubbleSort(); data.display(); cout<<"Exchangetimes:"<<data.GCExTimes()<<endl; cout<<"Comparetimes:"<<data.GCCoTimes()<<endl; data.Delete(); cout<<endl<<"Insertsort"<<endl; data.CreateData(r,n); data.InsertSort(); data.display(); cout<<"Exchangetimes:"<<data.GCExTimes()<<endl; cout<<"Comparetimes:"<<data.GCCoTimes()<<endl; data.Delete(); cout<<endl<<"Selectsort"<<endl; data.CreateData(r,n); data.SelectSort(); data.display(); cout<<"Exchangetimes:"<<data.GCExTimes()<<endl; cout<<"Comparetimes:"<<data.GCCoTimes()<<endl; data.Delete(); cout<<endl<<"Quicksort"<<endl; data.CreateData(r,n); data.QuickSort(); data.display(); cout<<"Exchangetimes:"<<data.GCExTimes()<<endl; cout<<"Comparetimes:"<<data.GCCoTimes()<<endl; data.Delete(); cout<<endl<<"Heapsort"<<endl; data.CreateData(r,n); data.HeapSort(); data.display(); cout<<"Exchangetimes:"<<data.GCExTimes()<<endl; cout<<"Comparetimes:"<<data.GCCoTimes()<<endl; data.Delete(); cout<<endl;}/******************************************************************************///Sort排序類的文件”Sort.h”#ifndefSORT#defineSORT/******************************************************************************//*數(shù)據(jù)類型的定義*/typedefintKey;typedefstruct{ Keykey;}Rec;/******************************************************************************//***************Sort排序類*****************************************************//*功能:1類中的成員函數(shù)完成對數(shù)據(jù)的排序2數(shù)據(jù)的錄入3記錄交換和比較次數(shù) 4顯示數(shù)據(jù)*//*排序函數(shù)分別有:冒泡排序,直接插入排序,選擇排序,快速排序,堆排序*/classSort{private: Rec*r;//儲存數(shù)據(jù)所用數(shù)組 intn;//記錄數(shù)據(jù)數(shù)量 intExchangeTimes; //交換次數(shù) intCompareTimes; //比較次數(shù) voidqksort0(ints,intt);//快速排序遞歸用函數(shù) voidqkpass(ints,intt,int&k);//快速排序遞歸函數(shù) voidsift(intk,intm); //堆排序所用遞歸函數(shù)public: Sort(); Sort(Recr[],intn); voidCreateData(Recr[],intn); voidBubbleSort();//冒泡排序 voidInsertSort();//直接插入排序 voidSelectSort();//簡單選擇排序 voidQuickSort();//快速排序 voidHeapSort();//堆排序 intGCExTimes();//獲取交換次數(shù)并對交換次數(shù)清零 intGCCoTimes();//獲取比較次數(shù)并對交換次數(shù)清零 voiddisplay(); //顯示數(shù)據(jù) voidDelete();//刪除剩余的儲存空間};/******************************************************************************//**********Sort類的構(gòu)造函數(shù)****************************************************//*功能:對數(shù)據(jù)的初始化*/Sort::Sort(){ r=NULL; n=0; ExchangeTimes=0; CompareTimes=0;}Sort::Sort(Recr[],intn){ this->r=newRec[n+1];this->n=n; for(inti=0;i<=n;i++) this->r[i]=r[i]; ExchangeTimes=0; CompareTimes=0;}/******************************************************************************//************CreateData函數(shù)****************************************************//*功能:調(diào)用類中的函數(shù)完成對數(shù)據(jù)的初始化*/voidSort::CreateData(Recr[],intn){ this->r=newRec[n+1];this->n=n; for(inti=0;i<=n;i++) this->r[i]=r[i]; ExchangeTimes=0; CompareTimes=0;}/******************************************************************************//*************BubbleSort冒泡排序***********************************************//*功能:用冒泡法對數(shù)據(jù)進(jìn)行排序（排序穩(wěn)定）*/voidSort::BubbleSort(){ boolflag;Rect; for(inti=1;i<=n-1;i++) { flag=true; for(intj=1;j<=n-i;j++) { CompareTimes++; if(r[j+1].key<r[j].key) { flag=false; t=r[j];r[j]=r[j+1];r[j+1]=t; ExchangeTimes++; } } if(flag)break; }}/******************************************************************************//********************InsertSort直接插入排序************************************//*功能:用直接插入排序的方法對數(shù)據(jù)進(jìn)行排序（排序穩(wěn)定）*/voidSort::InsertSort(){ for(inti=2;i<=n;i++) { r[0]=r[i]; CompareTimes++; for(intj=i-1;r[j].key>r[0].key;j--) { r[j+1]=r[j]; CompareTimes++; } r[j+1]=r[0]; }}/******************************************************************************//***********************SelectSort選擇排序*************************************//*功能:用選擇排序的方法對數(shù)據(jù)進(jìn)行排序（排序不穩(wěn)定）*/voidSort::SelectSort(){ intk; for(inti=1;i<=n-1;i++) { r[0]=r[i];k=i; for(intj=i+1;j<=n;j++) { CompareTimes++; if(r[j].key<r[k].key)k=j; } if(i!=k) { r[i]=r[k];r[k]=r[0]; ExchangeTimes++; } }}/******************************************************************************//****************QuickSort快速排序*********************************************//*功能:用快速排序的方法完成對數(shù)據(jù)的排序(遞歸函數(shù))（排序不穩(wěn)定）*//*在記錄快速排序的比較次數(shù)的時(shí)候,著實(shí)費(fèi)了些工夫,不過最后還是弄出來了*/voidSort::QuickSort(){ qksort0(1,n);}voidSort::qksort0(ints,intt){ intk; if(s<t) { this->qkpass(s,t,k); this->qksort0(s,k-1); this->qksort0(k+1,t); }}voidSort::qkpass(ints,intt,int&k)//快速排序中的遞歸函數(shù){ inti=s;intj=t; r[0]=r[s]; while(i<j) { while(i<j&&r[j].key>=r[0].key)//快速排序比價(jià)次數(shù)的記錄應(yīng)該在這 {CompareTimes++;j--;} if(i!=j)CompareTimes++;/*在循環(huán)外還有一個(gè)滿足(i!=j)條件后比較次數(shù)的自加, 這是因?yàn)檫@個(gè)循環(huán)的條件不止有關(guān)鍵字比較的條件來跳出循環(huán), 還有一另一個(gè)條件(i<j)來?xiàng)l出循環(huán),而因?yàn)檫@個(gè)條件跳出循環(huán)的時(shí), 是不需要進(jìn)行關(guān)鍵字比較的,所以這要多一個(gè)if的條件判斷*/ r[i]=r[j]; while(i<j&&r[i].key<=r[0].key) {CompareTimes++;i++;} r[j]=r[i]; if(i!=j)CompareTimes++; } if(i!=s) { r[i]=r[0]; ExchangeTimes++; } k=i;}/******************************************************************************//***************HeapSort堆排序*************************************************//*功能:用堆排序方法完成對數(shù)據(jù)的排序（排序不穩(wěn)定）*/voidSort::HeapSort(){ inti,m;Rect; m=n/2; for(i=m;i>=1;i--)sift(i,n); for(i=n;i>=2;i--) { t=r[1];r[1]=r[i];r[i]=t; ExchangeTimes++; sift(1,i-1); }}voidSort::sift(intk,intm){ inti,j;boolfinished; i=k;j=2*i; r[0]=r[k]; finished=false; while(j<=m&&!finished) { CompareTimes++; if(j<m&&(r[j].key<r[j+1].key))j++; CompareTimes++; if(r[0].key>=r[j].key)finished=true; else { r[i]=r[j];i=j;j=2*i; } } if(i!=k) { r[i]=r[0];ExchangeTimes++; }}/******************************************************************************//*****************display函數(shù)**************************************************//*功能:顯示排序好的數(shù)組*/voidSort::display(){ for(inti=1;i<=n;i++) cout<<r[i].key<<""; cout<<endl;}/******************************************************************************//***********GCExTimes函數(shù)******************************************************//*功能:獲取交換次數(shù)并對交換次數(shù)清零*/intSort::GCExTimes(){ intt=ExchangeTimes; ExchangeTimes=0; returnt;}/******************************************************************************//***********GCCoTimes函數(shù)******************************************************//*功能:獲取比較次數(shù)并對交換次數(shù)清零*/intSort::GCCoTimes(){ intt=CompareTimes; CompareTimes=0; returnt;}/******************************************************************************//**********Delete函數(shù)**********************************************************//*功能:刪除不需要用的儲存空間,減少空間的占有量*/voidSort::Delete(){ delete[]r; n=0;}/******************************************************************************/#endif實(shí)驗(yàn)結(jié)果及結(jié)果分析：********************************************************************************The1primaryarrayis:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950********************************************************************************Bubblesort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:49Insertsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:49Selectsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:1225Quicksort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:1225Heapsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:122Comparetimes:444********************************************************************************The2primaryarrayis:5049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321********************************************************************************Bubblesort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:1225Comparetimes:1225Insertsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:1274Selectsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:25Comparetimes:1225Quicksort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:25Comparetimes:1250Heapsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:96Comparetimes:386********************************************************************************The3primaryarrayis:1234567891011121314151617181920212223242550494847464544434241403938373635343332313029282726********************************************************************************Bubblesort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:300Comparetimes:925Insertsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:0Comparetimes:349Selectsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:12Comparetimes:1225Quicksort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:12Comparetimes:1237Heapsort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950Exchangetimes:122Comparetimes:430********************************************************************************The4primaryarrayis:33333333333333333333333333333333333333333333333333********************************************************************************Bubblesort33333333333333333333333333333333333333333333333333Exchangetimes:0Comparetimes:49Insertsort33333333333333333333333333333333333333333333333333Exchangetimes:0Comparetimes:49Selectsort33333333333333333333333333333333333333333333333333Exchangetimes:0Comparetimes:1225Quicksort33333333333333333333333333333333333333333333333333Exchangetimes:0Comparetimes:1225Heapsort33333333333333333333333333333333333333333333333333Exchangetimes:49Comparetimes:146********************************************************************************The5primaryarrayis:12722723212996967947767879221371589184960338441501803844252700904725858829723888157627217745876017841934970994198251137088616431459770991587021********************************************************************************Bubblesort14214990127129137164184193227232252314338370388441472501511585587589597601679700709709721762774776784787803815844870882886915922941960969972982Exchangetimes:530Comparetimes:1224Insertsort14214990127129137164184193227232252314338370388441472501511585587589597601679700709709721762774776784787803815844870882886915922941960969972982Exchangetimes:0Comparetimes:579Selectsort14214990127129137164184193227232252314338370388441472501511585587589597601679700709709721762774776784787803815844870882886915922941960969972982Exchangetimes:46Comparetimes:1225Quicksort14214990127129137164184193227232252314338370388441472501511585587589597601679700709709721762774776784787803815844870882886915922941960969972982Exchangetimes:25Comparetimes:339Heapsort142149901271291371641841932272322523143383703884414725015115855875895976016797007097097217627747767847878038158