排序算法性能的比較

注: 由于只是測(cè)試算法性能, 所以不會(huì)對(duì)排序算法做深入講解, 在隨后的時(shí)間將會(huì)推出排序的詳細(xì)講解

問題需求分析

排序算法經(jīng)過了很長時(shí)間的演變，產(chǎn)生了很多種不同的方法。每種算法主要針對(duì)不同的數(shù)列進(jìn)行排序，這些排序算法具有各自的利弊，并且應(yīng)用的場(chǎng)景各自不同，為了針對(duì)不同的場(chǎng)景選出最合適的排序算法，接下來將使用大量隨機(jī)數(shù)列，以及不同的數(shù)據(jù)場(chǎng)景對(duì)不同的排序算法進(jìn)行比較，最終找出排序算法各自的優(yōu)缺點(diǎn)以及不同應(yīng)用的場(chǎng)景。

數(shù)據(jù)結(jié)構(gòu)定義

選用8種不同亂序的數(shù)列，每種數(shù)列使用6組不同的數(shù)列進(jìn)行測(cè)試，每組數(shù)列大小在500左右(若數(shù)據(jù)量太小不能明顯測(cè)試，將會(huì)修改為更大的數(shù)據(jù))。

測(cè)試系統(tǒng)功能設(shè)計(jì)及排序算法原理概述

隨機(jī)數(shù)產(chǎn)生函數(shù):總共有8中亂序數(shù)據(jù), 其中兩組是屬于正序與反序狀態(tài), 這兩種狀態(tài)直接通過排序函數(shù)獲得, 剩余6種狀態(tài)采用的方法是通過設(shè)定隨機(jī)數(shù)范圍n,m控制隨機(jī)數(shù)整體體現(xiàn)一個(gè)升序或者是降序的狀態(tài), 但是局部出現(xiàn)的就是部分無序, 所以就可以限定數(shù)列有序的狀態(tài)

插入排序: 1.獲得一個(gè)數(shù), 就去數(shù)組從數(shù)組末尾比較直達(dá)找這個(gè)數(shù)合適的位置, 2.重復(fù)1中的步驟, 直到所有數(shù)在數(shù)組中都沒找到一個(gè)合適的位置.

希爾排序: 原理與插入排序的效果一樣, 插入排序每次從數(shù)組中選的數(shù)總是依次選, 選取的數(shù)間隔是1, 而希爾排序每次總是按照一定的間隔選取數(shù), 就比如第一次選n/2, 第二次選n/4, 直到選間隔數(shù)為1, 此時(shí)的希爾排序就只是單純的插入排序, 但是與插入排序不同的, 當(dāng)處理大量數(shù)據(jù)且數(shù)據(jù)一定程度上有序, 相比于插入排序, 希爾排序的速度將會(huì)是極大的提升.

冒泡排序: 1.遍歷整個(gè)數(shù)組, 相鄰之間的數(shù)不斷比較, 直到數(shù)組中最大(最小)的數(shù)移動(dòng)到數(shù)組的末尾(開頭). 2.重復(fù)1中步驟, 直到所有數(shù)都能在數(shù)組中(局部)變?yōu)樽畲蠡蜃钚〉臄?shù).

快速排序: 1.遍歷數(shù)組, 從右往左, 找比基準(zhǔn)元素小的元素A, 同時(shí)從左往右, 找比基準(zhǔn)元素大的元素B, 若找到則交換A,B的位置(此時(shí)i,j下標(biāo)還沒碰頭), 當(dāng)i,j碰頭的時(shí)候, i,j對(duì)應(yīng)的下標(biāo)就是基準(zhǔn)元素的位置, 此時(shí)將基準(zhǔn)元素與i,j下標(biāo)的元素交換, 這樣的一輪循環(huán)就完成了一個(gè)元素的尋找. 2.遞歸往下尋找, 以剛才找到的元素位置作為分界線, 二分再次進(jìn)行查找, 重復(fù)1中步驟.(1中的查找方式, 為步驟2二分操作打下基礎(chǔ), 每次基準(zhǔn)元素(此時(shí)的基準(zhǔn)元素已經(jīng)找到了合適的位置)左邊的元素總是會(huì)比右邊的元素小)
選擇排序: 1.遍歷數(shù)組, 找到數(shù)組中最大(最小)元素的位置, 然后交換該元素與數(shù)組末尾(開頭)的元素, 一趟遍歷就能找到一個(gè)元素的合適位置. 2.重復(fù)1中步驟, 直達(dá)所有元素都能找到自己合適的位置.

堆排序: 1.根據(jù)父節(jié)點(diǎn)與左右子樹下標(biāo)的關(guān)系(左節(jié)點(diǎn):2i,右節(jié)點(diǎn):2i+1)遍歷數(shù)組, 比較左右節(jié)點(diǎn), 父節(jié)點(diǎn)之間的大小關(guān)系, 3個(gè)元素中找出最小(最大)的元素作為父節(jié)點(diǎn)(存在父節(jié)點(diǎn)與子節(jié)點(diǎn)之間順序的交換), 此時(shí)局部的子樹就構(gòu)建成小頂堆(大頂堆). 2.進(jìn)行size/2次循環(huán)執(zhí)行步驟1, 使得能構(gòu)建大頂堆(小頂堆). 3.在構(gòu)建出大頂堆(小頂堆)的基礎(chǔ)上, 拿出最大數(shù)(最小數(shù))(這里的做法是, 將root處的值與數(shù)組末尾的值(葉子節(jié)點(diǎn), 下標(biāo)j–, 排好序的數(shù)列就不能打亂哦)交換), 剩下數(shù)再進(jìn)行1中步驟, 此處類似于選擇, 在構(gòu)建好的大頂堆(小頂堆)中拿出最大(最小)值. 4.重復(fù)3中步驟, 直到所有數(shù)都找出來.

函數(shù)調(diào)用圖

測(cè)試樣例數(shù)據(jù):

Level取值如下(5,6,7屬于整體逆序的狀態(tài)):1:正序; 2:有點(diǎn)亂; 3:亂的比較多; 4:完全隨機(jī); 5:亂的比較多; 6:有點(diǎn)亂; 7:逆序 ;8:正序 ;測(cè)試數(shù)據(jù)量為400.

結(jié)論分析

從上面這個(gè)表來看, 當(dāng)數(shù)量已經(jīng)是正序的時(shí)候采用冒泡排序是最快; 在逆序的狀態(tài)下還是采用快速排序, 若要求數(shù)列穩(wěn)定性, 應(yīng)該采用選擇排序; 在整體處于正序的時(shí)候使用冒泡, 選擇排序都是有優(yōu)勢(shì)的; 而整體處于逆序的時(shí)候還是選擇排序和快速排序; 當(dāng)數(shù)列完全逆序的時(shí)候, 選擇快速排序是最好的; 從上面整體來看, 快排的平均時(shí)間復(fù)雜度最低, 堆排序平均時(shí)間復(fù)雜度最高, 冒泡, 插入, 選擇時(shí)間復(fù)雜度差不多, 而希爾排序在大量數(shù)據(jù)的時(shí)候優(yōu)于插入排序.

調(diào)試代碼存在的問題

1.構(gòu)建隨機(jī)函數(shù)的時(shí)候, 由于n, m參數(shù)沒有控制好, 導(dǎo)致出現(xiàn)的數(shù)列具有一定的誤差, 這個(gè)問題只用通過大量的參數(shù)測(cè)試, 直到找出最合適的n與m.
2.進(jìn)行希爾排序的時(shí)候, 我選用的間隔是 n/=2, 每次選取的間隔數(shù)自動(dòng)縮短為1/2, 但是也導(dǎo)致了一個(gè)問題就是, 到最后n的值可能是0, 由此導(dǎo)致希爾排序出現(xiàn)死循環(huán), 這個(gè)問題調(diào)試了好一會(huì), 才發(fā)現(xiàn), 在這一次的調(diào)試中, 更加深入理解了希爾排序的真諦, 其他排序也一樣,寫的過程中, 也存在許多問題, 大部分問題最終還是體現(xiàn)在對(duì)排序算法的不熟悉導(dǎo)致, 由于沒有弄清楚排序的真正機(jī)制, 所以也就導(dǎo)致太多不應(yīng)該犯的錯(cuò)誤.

完整代碼

#include<iostream> #include <stdlib.h> #include <time.h> using namespace std; const long Size=400; //所有元素的0號(hào)位都是臨時(shí)元素 void show(int a[],int size){for(int i=1;i<size;i++){cout<<a[i]<<" ";if((i+1)%20==0)cout<<endl;} }//插入排序 void insertSort(int a[],int size, int &cs, int &ss){int i,j;for(i=1;i<size;i++){ a[0]=a[i]; j=i-1;while(true){//臨時(shí)元素從數(shù)列末尾-1進(jìn)行比較，直到遇到比他小的停止 ++cs;if(a[0]<a[j]){//移動(dòng)過程中出現(xiàn)交換 ++ss;a[j+1]=a[j--];}else break; }//找到比他小的元素，進(jìn)行交換++ss; a[j+1]=a[0];} }//希爾排序 void shellSort(int a[],int size, int &cs, int &ss){int i,j,dk=size/25;while(dk > 0){dk /= 2;if(dk > 0 && dk < 10) dk = 1;for(i = dk; i < size; i++){++cs; if(a[i] < a[i-dk]){a[0] = a[i];j = i-dk;++cs; while(a[0] < a[j]){++ss; a[j+dk] = a[j];j -= dk;}++ss; a[j+dk] = a[0];}}} }//冒泡排序 void bubbleSort(int a[],int size, int &cs, int &ss){int flag=0;for(int i=1;i<size;i++){flag=1;for(int j=1;j<size-i;j++){++cs; if(a[j]>a[j+1]){++ss; a[0]=a[j];a[j]=a[j+1];a[j+1]=a[0];flag=0;}}if(flag==1)break;} }//快速排序 void quickSort(int a[],int l,int r, int &cs, int &ss){if(l>r)return; int i=l,j=r,t;a[0]=a[l];++cs; while(i!=j){++cs; while(a[0]<=a[j]&&i<j){j--;} ++cs; while(a[0]>=a[i]&&i<j){i++;}++cs;if(i<j){++ss; t=a[i];a[i]=a[j];a[j]=t;//左右兩邊的值交換 }}++ss;a[l]=a[i];a[i]=a[0];//基數(shù)的交換 quickSort(a,l,i-1, cs, ss);quickSort(a,i+1,r, cs, ss); }//選擇排序 void selectSort(int a[],int size, int &cs, int &ss){int i,j,k;for(i=1;i<size;i++){k=i;for(j=i;j<size;j++){++cs; if(a[k]>a[j])k=j; }++cs; if(k!=i){++ss; a[0]=a[k];a[k]=a[i];a[i]=a[0];}} } //建堆操作 void heapAdjust(int a[],int i,int n, int &cs, int &ss){//建立大頂堆 int temp;//將局部最小的樹變?yōu)槎?temp=a[i];for(int j=i*2;j<=n;j++){//for循環(huán)主要針對(duì)局部子樹的調(diào)整,//將左右子樹中大值往前調(diào)整++cs;if(j<n&&a[j]<a[j+1])j++;//左右子樹進(jìn)行比較 ++cs;if(temp>=a[j])break;++ss;a[i]=a[j];//與根節(jié)點(diǎn)進(jìn)行交換 i=j;//i原本為j的root,現(xiàn)在j向子樹深入,root進(jìn)行改變//i變?yōu)閖 }++ss;a[i]=temp; } //堆排序 void heapSort(int a[],int size, int &cs, int &ss){for(int i=size/2;i>0;i--)heapAdjust(a,i,size, cs, ss);for(int j=size;j>1;j--){//每調(diào)整一下,就將root與最遠(yuǎn)的葉子進(jìn)行交換//此處的root為最大值 ++ss;a[0]=a[1];a[1]=a[j];a[j]=a[0];heapAdjust(a,1,j-1, cs, ss);} } //生成隨機(jī)數(shù),level代表亂序程度 控制m, n取值范圍, 可有效控制隨機(jī)數(shù)混亂程度 1 5個(gè)數(shù)中取隨機(jī)數(shù) 2 10 中取隨機(jī)數(shù) 3 完全隨機(jī) 4 完全隨機(jī) 5 10個(gè)取隨機(jī)數(shù) 6 5個(gè)取隨機(jī)數(shù) 7 逆序 **/ void createSrand(int a[],int size, int level){int m, n;if(level < 5){m = 0; n = 50;}else{m = 3951; n = 4001;}srand((unsigned)time(NULL)); // rand()%(n-m+1)+m, [m,n]范圍內(nèi)的隨機(jī)數(shù) for(int i= 0; i < size;i++ ){if(level == 1){m += 10;n += 10;}else if(level == 2){m += 5;n += 7;}else if(level == 4){m = 0;n = 4001;}else if(level == 4){m = 0;n = 4001;}else if(level == 5){m -= 5;n -= 7;}else if(level == 6){m -= 10;n -= 10;}else if(level == 7){int flag=0;for(int i=1;i<size;i++){flag=1;for(int j=1;j<size-i;j++){if(a[j]<a[j+1]){a[0]=a[j];a[j]=a[j+1];a[j+1]=a[0];flag=0;}}if(flag==1)break;} // show(a, size);return;}else if(level == 8){int i = 0;quickSort(a, 1, Size-1, i, i); // show(a, size);return;}a[i]=rand()%(n-m+1)+m;} // show(a, size); }//性能測(cè)試函數(shù) void testLevel(int a[], int size){int cs, ss;for(int i = 1; i < 9; i++){cs = 0, ss = 0;createSrand(a, size, i);cout<<"Level="<<i<<" insertSort:";insertSort(a,Size,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;cs = 0, ss = 0;createSrand(a,Size,i);cout<<"Level="<<i<<" shellSort:";shellSort(a,Size,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;cs = 0, ss = 0;createSrand(a,Size,i);cout<<"Level="<<i<<" bubbleSort:";bubbleSort(a,Size,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;cs = 0, ss = 0;createSrand(a,Size,i);cout<<"Level="<<i<<" quickSort:";quickSort(a,1,Size-1,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;cs = 0, ss = 0;createSrand(a,Size,i);cout<<"Level="<<i<<" selectSort:";selectSort(a,Size,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;cs = 0, ss = 0;createSrand(a,Size,i);cout<<"Level="<<i<<" heapSort:";heapSort(a,Size-1,cs,ss);cout<<" cs="<<cs<<" ss="<<ss<<endl;cout<<"-----------------------------------------------------------\n"<<endl;} } int main(){int a[Size];testLevel(a, Size);return 0; }

上面有錯(cuò), 還請(qǐng)指出, 如果認(rèn)為我寫的還不錯(cuò), 還請(qǐng)點(diǎn)個(gè)贊, 多多支持一下, O(∩_∩)O~~

總結(jié)

以上是生活随笔為你收集整理的常用排序算法以及算法性能测试(完整C/C++代码实现)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。