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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、和上述一樣的結(jié)果。對程序結(jié)果的評價(jià)經(jīng)過比較我們發(fā)現(xiàn)，當(dāng)規(guī)模不斷增加時(shí)，各種算法之間的差別是很大的。這七種算法中，快速排序耗時(shí)是最少的。也是最快的一種排序方法。堆排序和快速排序差不多，屬于同一個(gè)數(shù)量級。直接選擇排序是耗時(shí)最多的。通過這次作業(yè)我學(xué)到了很多東西： 鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力。 通過自己編寫的程序?qū)Ω鞣N排序性能的比較讓我更深入理解了他們的應(yīng)用。 參考文獻(xiàn)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ù)的具體實(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ù)的具體實(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ù)組大?。ň幪?hào)0-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;/*計(jì)算冒泡排序時(shí)間*/ double cost1; begin1 = clock(); popo(series_a,N-1); end1 = clock(); cost1 = (double)(end1 - begin1)/ CLOCKS_PER_SEC; printf("冒泡排序耗時(shí):%lf secondsn",cost1); clock_t begin2,end2;/*計(jì)算選擇排序時(shí)間*/ double cost2; begin2=clock(); select(series_b,N); end2=clock(); cost2=(double)(end2 - begin2)/ CLOCKS_PER_SEC; printf("選擇排序耗時(shí):%lf secondsn",cost2); clock_t begin3, end3;/*計(jì)算直接插入排序時(shí)間*/ double cost3; begin3=clock(); InsertSort(series_c,N); end3=clock(); cos