排序算法論文

1、<p><b>　　排序算法</b></p><p><b>　　姓名：鄧 海 波</b></p><p>　　學(xué)號(hào)：2013222053</p><p><b>　　年級(jí)：2013 級(jí)</b></p><p><b>　　專業(yè): 生物信息學(xué)</b&g

2、t;</p><p><b>　　算法介紹</b></p><p>　　排序算法是為了解決輸入的n個(gè)數(shù)的一個(gè)序列{,,...,},經(jīng)過(guò)我們的排序后輸出已排好的序列{,,...,}(滿足≤≤...≤)。我們將通過(guò)不同的排序算法解決這個(gè)問(wèn)題，比如選擇排序、插入排序、冒泡排序、快速排序、堆排序、歸并排序、希爾排序、基數(shù)排序等，并通過(guò)對(duì)其時(shí)間復(fù)雜度進(jìn)行對(duì)比進(jìn)而得出相應(yīng)的結(jié)論。

3、</p><p><b>　　基本算法</b></p><p><b>　　選擇排序</b></p><p>　　選擇排序的基本思想是： 對(duì)待排序的n個(gè)數(shù)據(jù)進(jìn)行n-1遍的處理，第1遍處理是將a[2..n]中最小者與a[1]交換位置，第2遍處理是將a[3..n]中最小者與a[2]交換位置，......，第i遍處理是將a[i+

4、1..n]中最小者與a[i]交換位置。這樣，經(jīng)過(guò)i遍處理之后，前i個(gè)記錄的位置就已經(jīng)按從小到大的順序排列好了?？偣脖容^ n(n-1)/2 次，時(shí)間復(fù)雜度為(),其穩(wěn)定性為不穩(wěn)定（穩(wěn)定性是指值相同的數(shù)字在排序前后其相對(duì)位置是否要發(fā)生改變，若要改變就是不穩(wěn)定，否則就是穩(wěn)定的。）</p><p><b>　　算法代碼：</b></p><p><b>　　main

5、()</b></p><p><b>　　{</b></p><p>　　int flag,temp,i,j,a[10]={12,33,45,67,89,99,45,11,22,48};</p><p>　　printf("源程序?yàn)椋篭n");</p><p>　　for(i=0;i<

6、;10;i++)</p><p>　　printf("%-3d",a[i]);</p><p>　　for(i=0;i<9;i++)</p><p><b>　　{</b></p><p><b>　　flag=i;</b></p><p>　　fo

7、r(j=i+1;j<10;j++)</p><p><b>　　{</b></p><p>　　if(a[flag]>a[j])</p><p><b>　　{</b></p><p><b>　　flag=j;</b></p><p>&l

8、t;b>　　}</b></p><p><b>　　}</b></p><p>　　if(i!=flag)</p><p><b>　　{</b></p><p>　　temp=a[flag];</p><p>　　a[flag]=a[i];</p&g

9、t;<p>　　a[i]=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n排序后為：\n");</p><p>　　for(i=0;i<10;i++)</p>&

10、lt;p><b>　　{</b></p><p>　　printf("%-3d",a[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　冒泡排序</b></

11、p><p>　　冒泡排序基本思想是:對(duì)待排序的數(shù)字進(jìn)行兩兩比較,如發(fā)現(xiàn)兩個(gè)數(shù)字是反序的,則進(jìn)行交換,直到無(wú)反序的記錄為止（此處是按從大到小的順序排列）?？偣脖容^ n(n-1)/2 次，時(shí)間復(fù)雜度為(),是穩(wěn)定的排序算法。</p><p><b>　　算法代碼：</b></p><p><b>　　main()</b></

12、p><p><b>　　{</b></p><p>　　int i,j,l,a[10]={9,89,90,23,56,12,45,67,36,99};</p><p>　　printf("源程序?yàn)椋篭n");</p><p>　　for(i=0;i<10;i++)</p><p&

13、gt;<b>　　{</b></p><p>　　printf("%-3d",a[i]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("排序后為：\n");&l

14、t;/p><p>　　for(i=0;i<10;i++)</p><p><b>　　{</b></p><p>　　for(j=i+1;j<10;j++)</p><p><b>　　{</b></p><p>　　if(a[i]>a[j])</p>

15、;<p><b>　　{</b></p><p><b>　　l=a[i];</b></p><p>　　a[i]=a[j];</p><p><b>　　a[j]=l;</b></p><p><b>　　}</b></p>

16、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<10;i++)</p><p><b>　　{</b></p><p>　　printf("%-3d",a[i]);</p&

17、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　插入排序</b></p><p>　　有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法--插入排序

18、法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為()。是穩(wěn)定的排序方法。</p><p><b>　　算法代碼：</b></p><p>　　void insert(int a[],int leng)</p><p><b>　　{</

19、b></p><p>　　int i,j,key;</p><p>　　for(i=1;i<leng;i++)</p><p><b>　　{</b></p><p><b>　　key=a[i];</b></p><p><b>　　j=i-1;<

20、;/b></p><p>　　while(j>=0 && a[j]<key)</p><p><b>　　{</b></p><p>　　a[j+1]=a[j];</p><p><b>　　j--;</b></p><p><b>

21、;　　}</b></p><p>　　a[j+1]=key;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　main()</b></p><p><b>　　{</

22、b></p><p>　　int a[]={23,56,88,97,45,33,11,3,89,67},i,j;</p><p>　　printf("源數(shù)組為：\n");</p><p>　　for(i=0;i<10;i++)</p><p><b>　　{</b></p>

23、<p>　　printf("%-3d",a[i]);</p><p><b>　　}</b></p><p>　　insert(a,10);</p><p>　　printf("\n插入后序列為：\n");</p><p>　　for(j=0;j<10;j++)&l

24、t;/p><p><b>　　{</b></p><p>　　printf("%-3d",a[j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　快速排序<

25、/b></p><p>　　思想：每次找一個(gè)數(shù)位基準(zhǔn)，把小于等于它的放到這個(gè)數(shù)的左邊，把大于等于它的放到它的右邊，每排完一趟，小于等于基準(zhǔn)值的，在其左側(cè)。大于等于基準(zhǔn)值的在其右側(cè)。平均時(shí)間復(fù)雜度：()是不穩(wěn)定的排序算法。</p><p><b>　　算法代碼：</b></p><p>　　void quiksort(int a[],int

26、 low,int high)</p><p><b>　　{</b></p><p>　　int i = low;</p><p>　　int j = high;</p><p>　　int temp = a[i];</p><p>　　if( low < high)</p>

27、<p><b>　　{</b></p><p>　　while(i < j)</p><p><b>　　{</b></p><p>　　while((a[j] >= temp) && (i < j))</p><p><b>　　{</b

28、></p><p><b>　　j--;</b></p><p><b>　　}</b></p><p>　　a[i] = a[j];</p><p>　　while((a[i] <= temp) && (i < j))</p><p>&l

29、t;b>　　{</b></p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　a[j]= a[i];</p><p><b>　　}</b></p><p>　　a[i] = temp

30、;</p><p>　　quiksort(a,low,i-1);</p><p>　　quiksort(a,j+1,high);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b>

31、</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p&g

32、t;<p>　　int arry[11] = {2,32,43,23,45,36,57,14,27,39,11},i;</p><p>　　printf("源程序?yàn)椋篭n");</p><p>　　for(i=0;i<11;i++)</p><p><b>　　{</b></p><p

33、>　　printf("%d ",arry[i]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　quiksort(arry,0,10);</p><p>　　printf("排序后為：\n")

34、;</p><p>　　for(i=0;i<11;i++)</p><p><b>　　{</b></p><p>　　printf("%d ",arry[i]);</p><p><b>　　}</b></p><p>　　printf("

35、;\n");</p><p><b>　　}</b></p><p><b>　　堆排序</b></p><p>　　堆的定義:n個(gè)元素的序列{,,...,}，當(dāng)≤&≤時(shí)我們稱為最小化堆或小頂堆，當(dāng)≥&≥時(shí)我們稱為最大化堆或大頂堆(i=1,2,...,n)。由此，若序列{,,...,}是堆，則堆頂

36、元素（或完全二叉樹(shù)的根）必為序列中n個(gè)元素的最小值（或最大值）。若在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過(guò)程稱之為堆排序。</p><p>　　排序過(guò)程：堆排序是一種選擇排序。建立的初始堆為初始的無(wú)序區(qū)。</p><p>　　排序開(kāi)始，首先輸出堆頂元素（因?yàn)樗亲钪担瑢⒍秧斣睾妥詈笠粋€(gè)元素交換，

37、這樣，第n個(gè)位置（即最后一個(gè)位置）作為有序區(qū)，前n-1個(gè)位置仍是無(wú)序區(qū)，對(duì)無(wú)序區(qū)進(jìn)行調(diào)整，得到堆之后，再交換堆頂和最后一個(gè)元素，這樣有序區(qū)長(zhǎng)度變?yōu)?，不斷進(jìn)行此操作，將剩下的元素重新調(diào)整為堆，然后輸出堆頂元素到有序區(qū)。每次交換都導(dǎo)致無(wú)序區(qū)-1，有序區(qū)+1。不斷重復(fù)此過(guò)程直到有序區(qū)長(zhǎng)度增長(zhǎng)為n-1，排序完成。</p><p>　　想得到升序，則建立大頂堆，若想得到降序，則建立小頂堆。堆排序在最壞的情況下，其時(shí)間復(fù)雜

38、度：()是不穩(wěn)定的排序算法。相對(duì)于快速排序來(lái)說(shuō)，這是堆排序的最大優(yōu)點(diǎn)。此外，堆排序僅需一個(gè)記錄大小的供交換用的輔助存儲(chǔ)空間。</p><p><b>　　算法代碼：</b></p><p>　　/*堆排序 實(shí)現(xiàn)，算法復(fù)雜度O(nlgn)*/</p><p>　　#include<stdio.h></p><p&g

39、t;　　#include<stdlib.h></p><p>　　/*假設(shè)節(jié)點(diǎn)i的左右子樹(shù)都是最大堆，操作使節(jié)點(diǎn)i的子樹(shù)變成最大堆*/</p><p>　　void maxHeap(int A[],int len,int i)</p><p><b>　　{</b></p><p>　　int l,r,lar

40、ge,temp;</p><p><b>　　l=2*i;</b></p><p><b>　　r=2*i+1;</b></p><p><b>　　large=i;</b></p><p><b>　　if(l<len)</b></p>

41、<p><b>　　{</b></p><p>　　if(A[l]>A[i])</p><p><b>　　{</b></p><p><b>　　large=l;</b></p><p><b>　　}</b></p>

42、<p><b>　　}</b></p><p><b>　　if(r<len)</b></p><p><b>　　{</b></p><p>　　if(A[r]>A[large])</p><p><b>　　{</b></p

43、><p><b>　　large=r;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(large!=i)</p><p><b>　　{</b></p>

44、<p>　　temp=A[large];</p><p>　　A[large]=A[i];</p><p>　　A[i]=temp;</p><p>　　maxHeap(A,len,large);</p><p><b>　　}</b></p><p><b>　　}</

45、b></p><p><b>　　/*建立大根堆*/</b></p><p>　　void buildMaxHeap(int A[],int len)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><

46、p>　　for(i=len/2-1;i>=0;i--)</p><p>　　maxHeap(A,len,i);</p><p><b>　　}</b></p><p><b>　　/*堆排序*/</b></p><p>　　void maxHeapSort(int A[],int len

47、)</p><p><b>　　{</b></p><p>　　int i,temp;</p><p>　　buildMaxHeap(A,len);</p><p>　　printf("建立大跟堆:\n");</p><p>　　for(i=0;i<len;i++)<

48、;/p><p>　　printf("%-3d",A[i]);</p><p>　　printf("\n");</p><p>　　printf("大跟堆序列為:\n");</p><p>　　for(i=len;i>1;i--)</p><p><b&

49、gt;　　{</b></p><p>　　temp=A[0];</p><p>　　A[0]=A[i-1];</p><p>　　A[i-1]=temp;</p><p>　　printf("%-3d",A[i-1]);</p><p>　　buildMaxHeap(A,i-1);<

50、;/p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　/*測(cè)試堆排序*/</b></p><p>　　int main()</p&

51、gt;<p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　int A[11]={4,11,38,23,16,98,10,14,81,78,66};</p><p>　　printf("源序列為：\n");</p><p&

52、gt;　　for(i=0;i<11;i++)</p><p><b>　　{</b></p><p>　　printf("%-3d",A[i]);</p><p><b>　　}</b></p><p>　　printf("\n");</p>

53、<p>　　maxHeapSort(A,11);</p><p>　　printf("排序后為：\n");</p><p>　　for(i=0;i<11;i++)</p><p><b>　　{</b></p><p>　　printf("%-3d",A[i])

54、;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　總結(jié)</b></p><p>　　選擇排序、快速排序、希爾排序、堆排序不是