數(shù)據(jù)結(jié)構(gòu)各種排序算法性能比拼

1、 各種排序算法性能比拼 吳元平（數(shù)學(xué)與應(yīng)用數(shù)學(xué)，07121011） 摘要：排序算法是數(shù)據(jù)結(jié)構(gòu)這門課程核心內(nèi)容之一，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)排序算法是為了將實際問題中涉及的對象在計算機中對它們進行處理。我將利用Visual Studio 2012開發(fā)程序?qū)Ω鞣N算法進行測試。該測試系統(tǒng)可以通過操作把數(shù)據(jù)結(jié)構(gòu)中的主要排序常見的排序算法（直接插入排序、希爾排序、直接選擇排序、冒泡排序、快速排序、堆排序、歸并排序）的性能用時間的長短表現(xiàn)出來。 引言排序是計算機程序設(shè)計中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任意

2、序列，重新排列成一個按關(guān)鍵字有序的序列。 排序算法是在整個計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。排序算法是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。排序是計算機科學(xué)中最重要的研究問題之一, 它在計算機圖形、計算機輔助設(shè)計、機器人、模式識別及統(tǒng)計學(xué)等領(lǐng)域具有廣泛的應(yīng)用。由于它固有的理論上的重要性,其功能是將一個數(shù)據(jù)元素的任意序列重新排列成一個按關(guān)鍵字有序的序列。隨著計算機技術(shù)的日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運算。而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及插入、刪除、排序、查找等復(fù)雜的非數(shù)值處理和操作。排

3、序算法的學(xué)習(xí)就是為以后利用計算機資源高效地開發(fā)非數(shù)值處理的計算機程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。 需求分析 各種排序算法時間性能的比較 一、需求描述 對各種排序方法（直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序和歸并排序）的時間性能進行比較。 二、要求 1.設(shè)計并實現(xiàn)上述各種排序算法； 2.產(chǎn)生正序和逆序的初始排列分別調(diào)用上述排序算法，并比較時間性能； 3.產(chǎn)生隨機的初始排列分別調(diào)用上述排序算法，并比較時間性能。 三、設(shè)計思想 上述各種排序方法都是基于比較的內(nèi)排序，其時間

4、主要消耗在排序過程中進行的記錄的比較次數(shù)和移動次數(shù)，因此，統(tǒng)計在相同數(shù)據(jù)狀態(tài)下不同排序算法的比較次數(shù)和移動次數(shù)，即可實現(xiàn)比較各種排序算法的目的。  設(shè)計一、直接插入排序1.原理 假設(shè)待排序的n個記錄R0，R1，Rn順序存放在數(shù)組中，直接插入法在插入記錄Ri(i=1，2，n-1)時，記錄被劃分為兩個區(qū)間R0,Ri-1和Ri+1,Rn-1,其中，前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當(dāng)前未排序的部分，將關(guān)鍵碼Ki與Ki-1Ki-2，K0依次比較，找出應(yīng)該插入的位置，將記錄Ri插，然后將剩下的i-1個元素按關(guān)鍵詞大小依次插入該有序序列，沒插入一個元素后依然保持該序列有序，經(jīng)過i-1趟排序后

5、即成為有序序列。每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。2. 時間復(fù)雜度分析 直接插入排序算法必須進行n-1趟。最好情況下，即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復(fù)雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復(fù)雜度為O(n2)。2、 Shell排序1.原理 Shell排序又稱縮小增量排序,Shell排序法是以創(chuàng)建者Donald Shell的名字命名的.Shell排序法是對相鄰指定距離(稱為

6、間隔)的元素進行比較,已知到使用當(dāng)前間隔進行比較的元素都按順序排序為止.Shell把間隔縮小一半,然后繼續(xù)處理,當(dāng)間隔最終變?yōu)?,并且不再出現(xiàn)變化時,Shell排序也就完成了其處理過程.先取一個整數(shù)d1<n,把全部記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在一組中，先在各組內(nèi)排序；然后去d2<d1重復(fù)上訴分組和排序工作；直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有記錄放在同一組中進行直接插入，直到dt=1，即所有記錄放在一組中為止.2. 時間復(fù)雜度分析 希爾排序是按照不同步長對元素進行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入

7、排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時間復(fù)雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。所以希爾排序是不穩(wěn)定的，其時間復(fù)雜度為o(n2)。3、 直接選擇排序1. 原理 待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記

8、錄。第一趟第n個記錄中找出關(guān)鍵碼最小的記錄與第n個記錄交換；第二趟，從第二個記錄開始的，2 -1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第 i 趟，則從第i個記錄開始的 n - i + l個記錄中選出關(guān)鍵碼最小的記錄與第 i 個記錄交換，直到所有記錄排好序。2. 時間復(fù)雜度分析 該算法運行時間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復(fù)雜度都為O(n2)。4、 冒泡排序1. 原理 在每一趟冒泡排序中，依次比較相鄰的兩個關(guān)鍵字大小，若為反序咋交換。經(jīng)過一趟起泡

9、后，關(guān)鍵詞大的必須移到最后。按照這種方式進行第一趟在序列（I0In-1）中從前往后進行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元素被交換到In-1中，下一趟只需在子序列（I0In-2）中進行；如果在某一趟排序中未交換元素，則不再進行下一趟排序。將被排序的記錄數(shù)組J1.n垂直排列，每個記錄Ji看作是重量為Ji.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止，最后可完成。2. 時間復(fù)雜度分析 當(dāng)原始數(shù)據(jù)正向有序時，冒泡

10、排序出現(xiàn)最好情況。此時，只需進行一趟排序，作n-1次關(guān)鍵字比較，因此最好情況下的時間復(fù)雜度是O(n)。當(dāng)原始數(shù)據(jù)反向有序時，冒泡排序出現(xiàn)最壞情況。此時，需進行n-1趟排序，第i趟作(n-i)次關(guān)鍵字間的比較，并且需執(zhí)行(n-i)次元素交換，所以，比較次數(shù)為：因此,最壞情況下的時間復(fù)雜度為O(n2)。五、快速排序1.原理 首先我們選擇一個中間值 middle （程序中我們可使用數(shù)組中間值），把比中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復(fù)雜，我們先給出其進行一次排序的程序框架。在待排序的個記錄中任意取一個記錄（通常取第一個記錄）為區(qū)分標(biāo)準(zhǔn)，把所有小于該排序的記錄移到左邊，把

11、所有大于該排序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。然后對前后兩個子序列分別重新上述過程，直到所有記錄都排好序。對任意給定的序列中某個元素，經(jīng)過一趟排序后，將原序列分割成兩個子序列(Rp(0),Rp(1),Rp(s-1)和(Rp(s+1),Rp(s+2),Rp(n-1)，其中前一個子序列中的所有元素的關(guān)鍵詞均小于或等于該元素的關(guān)鍵詞值Kp(s)，后一個子序列中元素的關(guān)鍵詞均大于或等于Kp(s)。稱該元素Rp(s)為分割元素，子序列(Rp(0),Rp(1),Rp(s-1)為其低端序列，(Rp(0),Rp(1),Rp(s-1)為其高端序列。很明顯，以后只需對低端和高端序列分別進行快速排

12、序，直到子序列為空或只有一個元素時結(jié)束，最后得到有序序列?？傊刻耸贡淼牡谝粋€元素放在適當(dāng)位置，將表兩分，再對子表進行同樣的遞歸劃分，直至劃分的子表長度為1。2. 時間復(fù)雜度分析 如果每一次分劃操作后，左、右兩個子序列的長度基本相等，則快速排序的效率最高，其最好情況時間復(fù)雜度為O(nlog2n)；反之，如果每次分劃操作所產(chǎn)生的兩個子序列，其中之一為空序列，此時，快速排序效率最低，其最壞情況時間復(fù)雜度為O(n2)。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發(fā)生在原始序列正向有序或反向有序時?？焖倥判虻钠骄闆r時間復(fù)雜度為O(nlog2n)。六、堆排序1.原理 堆排序思想很簡單，就是每次

13、把關(guān)鍵詞調(diào)整為堆，取出堆頂元素與堆中最后一個元素交換，同時令堆得大小減一，把剩余的一些元素重新調(diào)整為堆，重復(fù)此過程，直到堆中只剩一個元素,n個關(guān)鍵字序列 kl , k2 ， ， kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）: ( l) ki<= k2i 且 ki<=k2i+1或（2）ki>= k2i 且 ki>=k2i+1。若將此序列所存儲的向量 R 1n看作是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中非葉結(jié)點的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點的關(guān)鍵字。根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為

14、小根堆。根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為大根堆。2. 時間復(fù)雜度分析 堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復(fù)雜度為O(nlogn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是不穩(wěn)定的，算法時間復(fù)雜度O(nlogn)。 程序運行結(jié)果以及結(jié)果分析一、下圖是對隨機生成的10000個數(shù)進行排序，可以看出快速排序法耗時最少而直接插入排序耗時最多，堆排序和快速排序差不多。二、下圖是對20000個隨機數(shù)進行的排序，可以看出得出了

15、和上述一樣的結(jié)果。對程序結(jié)果的評價經(jīng)過比較我們發(fā)現(xiàn)，當(dāng)規(guī)模不斷增加時，各種算法之間的差別是很大的。這七種算法中，快速排序耗時是最少的。也是最快的一種排序方法。堆排序和快速排序差不多，屬于同一個數(shù)量級。直接選擇排序是耗時最多的。通過這次作業(yè)我學(xué)到了很多東西： 鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。 通過自己編寫的程序?qū)Ω鞣N排序性能的比較讓我更深入理解了他們的應(yīng)用。 參考文獻1嚴(yán)蔚敏，吳偉民， 數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社2007 附錄#include<stdlib.h>#include<stdio.h>#include<time.h

16、>#define SWAP(x,y) int t;t=x; x=y; y=t;#define N 30000void nixu(int a,int b)/ 反序int i;for(i=0;i<N;i+)bN-1-i=ai;void popo(int a,int len)/*冒泡排序*/ int length=len; int i=0; int j=0; for(;i<len;i+)for(;j<length;j+)if(aj>aj+1)int temp=aj; aj=aj+1; aj+1=temp; length-; j=0;void select(int arr

17、ay,int n)/選擇排序 int i,j,t,k; for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) if(arrayj<arrayk)k=j; /k存放一輪中的最小數(shù)的下標(biāo); t=arrayi; arrayi=arrayk; arrayk=t; void Swap(int *a,int *b) int temp; temp = *a; *a = *b; *b = temp;void InsertSort(int data,int length)/直接插入排序 int i = 0; int j = 0; for(i = 1;i < l

18、ength;+i) for(j = i;j > 0;-j) if(dataj < dataj - 1) Swap(&dataj, &dataj - 1); else break; void quickSort(int a,int left,int right) /*快速排序*/ int i,j,temp; i=left; j=right; temp=aleft; if(left>right) return; while(i!=j)/*找到最終位置*/ while(aj>=temp && j>i) j-; if(j>i) ai+

19、=aj; while(ai<=temp && j>i) i+; if(j>i) aj-=ai; ai=temp; quickSort(a,left,i-1);/*遞歸左邊*/ quickSort(a,i+1,right);/*遞歸右邊*/ /歸并排序 /歸并排序合并數(shù)組函數(shù)的具體實現(xiàn) void merge(int a,int low,int middle,int high) int h,i,j,k; int bN; h=low; i=low; j=middle+1; while(h<=middle&&j<=high) if(ah&l

20、t;=aj) bi=ah; h+; else bi=aj; j+; i+; if(h>middle) for(k=j;k<=high;k+) bi=ak; i+; else for(k=h;k<=middle;k+) bi=ak; i+; for(k=low;k<=high;k+) ak=bk; /歸并排序函數(shù)的具體實現(xiàn) void mergesort(int a,int low,int high) int middle; if(low<high) middle=(low+high)/2; mergesort(a,low,middle); mergesort(a,m

21、iddle+1,high); merge(a,low,middle,high); void swapa(int a, int i, int j)/希爾排序 int t = ai; ai = aj; aj = t;void selsort(int a, int n, int incr) int i, j; for (i = incr; i < n; i += incr) for (j = i; (j >= incr) && (aj < aj-incr); j -= incr) swapa(a, j, j-incr);void shellsort(int a, i

22、nt n) int i, j; for (i = n / 2; i > 2; i /= 2) for (j = 0; j < i; j+) selsort(&aj, n - j, i); selsort(a, n, 1);void shift(int a,int i,int m)/堆排序 int k,t; t=ai; k=2*i+1; while (k<m) if (k<m-1) && (ak < ak+1) k +; if (t<ak) ai=ak;i=k;k=2*i+1; else break; ai=t;void heap(in

23、t a,int n) /a 為排序數(shù)組，n為數(shù)組大?。ň幪?-n-1）int i,k; for (i=n/2-1;i>=0;i-) shift(a,i,n); for(i=n-1;i>= 1;i-) k=a0;a0=ai;ai=k; shift(a,0,i); int main()int series N=0; int series_0N; int series_aN; int series_bN; int series_cN; int series_dN; int series_eN; int series_fN; int series_gN; int i,num; srand(

24、time(NULL); for(i=0;i<N;i+) seriesi=rand()%N; for(i=0;i<N;i+) series_0i=seriesi; for(num=0;num<2;num+) if(num>0) nixu(series_0,series); printf("待排數(shù)據(jù)：n"); for(i=0;i<N;i+) printf("%d ",seriesi); putchar(N); for(i=0;i<N;i+) series_ai=seriesi; series_bi=seriesi; ser

25、ies_ci=seriesi; series_di=seriesi; series_ei=seriesi; series_fi=seriesi; series_gi=seriesi; clock_t begin1, end1;/*計算冒泡排序時間*/ double cost1; begin1 = clock(); popo(series_a,N-1); end1 = clock(); cost1 = (double)(end1 - begin1)/ CLOCKS_PER_SEC; printf("冒泡排序耗時:%lf secondsn",cost1); clock_t begin2,end2;/*計算選擇排序時間*/ double cost2; begin2=clock(); select(series_b,N); end2=clock(); cost2=(double)(end2 - begin2)/ CLOCKS_PER_SEC; printf("選擇排序耗時:%lf secondsn",cost2); clock_t begin3, end3;/*計算直接插入排序時間*/ double cost3; begin3=clock(); InsertSort(series_c,N); end3=clock(); cos