《排序算法論》word版.docxVIP

排序算法 姓名：鄧 海 波 學(xué)號(hào)：2013222053 年級(jí)：2013 級(jí) 專業(yè): 生物信息學(xué)1、 算法介紹排序算法是為了解決輸入的n個(gè)數(shù)的一個(gè)序列,.,經(jīng)過我們的排序后輸出已排好的序列,.,(滿足.)。我們將通過不同的排序算法解決這個(gè)問題，比如選擇排序、插入排序、冒泡排序、快速排序、堆排序、歸并排序、希爾排序、基數(shù)排序等，并通過對(duì)其時(shí)間復(fù)雜度進(jìn)行對(duì)比進(jìn)而得出相應(yīng)的結(jié)論。2、 基本算法1、 選擇排序選擇排序的基本思想是： 對(duì)待排序的n個(gè)數(shù)據(jù)進(jìn)行n-1遍的處理，第1遍處理是將a2.n中最小者與a1交換位置，第2遍處理是將a3.n中最小者與a2交換位置，.，第i遍處理是將ai+1.n中最小者與ai交換位置。這樣，經(jīng)過i遍處理之后，前i個(gè)記錄的位置就已經(jīng)按從小到大的順序排列好了。總共比較 n(n-1)/2 次，時(shí)間復(fù)雜度為(),其穩(wěn)定性為不穩(wěn)定（穩(wěn)定性是指值相同的數(shù)字在排序前后其相對(duì)位置是否要發(fā)生改變，若要改變就是不穩(wěn)定，否則就是穩(wěn)定的。）算法代碼： main() int flag,temp,i,j,a10=12,33,45,67,89,99,45,11,22,48; printf(源程序?yàn)椋簄); for(i=0;i10;i+) printf(%-3d,ai); for(i=0;i9;i+) flag=i; for(j=i+1;jaj) flag=j; if(i!=flag) temp=aflag; aflag=ai; ai=temp; printf(n排序后為：n); for(i=0;i10;i+) printf(%-3d,ai); 2、 冒泡排序冒泡排序基本思想是:對(duì)待排序的數(shù)字進(jìn)行兩兩比較,如發(fā)現(xiàn)兩個(gè)數(shù)字是反序的,則進(jìn)行交換,直到無反序的記錄為止（此處是按從大到小的順序排列）?？偣脖容^ n(n-1)/2 次，時(shí)間復(fù)雜度為(),是穩(wěn)定的排序算法。算法代碼：main() int i,j,l,a10=9,89,90,23,56,12,45,67,36,99; printf(源程序?yàn)椋簄); for(i=0;i10;i+) printf(%-3d,ai); printf(n); printf(排序后為：n); for(i=0;i10;i+) for(j=i+1;jaj) l=ai; ai=aj; aj=l; for(i=0;i10;i+) printf(%-3d,ai); 3、 插入排序有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法-插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為()。是穩(wěn)定的排序方法。算法代碼：void insert(int a,int leng) int i,j,key; for(i=1;i=0 & ajkey) aj+1=aj; j-; aj+1=key; main() int a=23,56,88,97,45,33,11,3,89,67,i,j; printf(源數(shù)組為：n); for(i=0;i10;i+) printf(%-3d,ai); insert(a,10); printf(n插入后序列為：n); for(j=0;j10;j+) printf(%-3d,aj); 4、 快速排序思想：每次找一個(gè)數(shù)位基準(zhǔn)，把小于等于它的放到這個(gè)數(shù)的左邊，把大于等于它的放到它的右邊，每排完一趟，小于等于基準(zhǔn)值的，在其左側(cè)。大于等于基準(zhǔn)值的在其右側(cè)。平均時(shí)間復(fù)雜度：()是不穩(wěn)定的排序算法。算法代碼：void quiksort(int a,int low,int high) int i = low; int j = high; int temp = ai; if( low high) while(i = temp) & (i j) j-; ai = aj; while(ai = temp) & (i j) i+; aj= ai; ai = temp; quiksort(a,low,i-1); quiksort(a,j+1,high); else return; void main() int arry11 = 2,32,43,23,45,36,57,14,27,39,11,i; printf(源程序?yàn)椋簄); for(i=0;i11;i+) printf(%d ,arryi); printf(n); quiksort(arry,0,10); printf(排序后為：n); for(i=0;i11;i+) printf(%d ,arryi); printf(n);5、 堆排序堆的定義:n個(gè)元素的序列,.,，當(dāng)&時(shí)我們稱為最小化堆或小頂堆，當(dāng)&時(shí)我們稱為最大化堆或大頂堆(i=1,2,.,n)。由此，若序列,.,是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個(gè)元素的最小值（或最大值）。若在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱之為堆排序。排序過程：堆排序是一種選擇排序。建立的初始堆為初始的無序區(qū)。排序開始，首先輸出堆頂元素（因?yàn)樗亲钪担?，將堆頂元素和最后一個(gè)元素交換，這樣，第n個(gè)位置（即最后一個(gè)位置）作為有序區(qū)，前n-1個(gè)位置仍是無序區(qū)，對(duì)無序區(qū)進(jìn)行調(diào)整，得到堆之后，再交換堆頂和最后一個(gè)元素，這樣有序區(qū)長(zhǎng)度變?yōu)?，不斷進(jìn)行此操作，將剩下的元素重新調(diào)整為堆，然后輸出堆頂元素到有序區(qū)。每次交換都導(dǎo)致無序區(qū)-1，有序區(qū)+1。不斷重復(fù)此過程直到有序區(qū)長(zhǎng)度增長(zhǎng)為n-1，排序完成。想得到升序，則建立大頂堆，若想得到降序，則建立小頂堆。堆排序在最壞的情況下，其時(shí)間復(fù)雜度：()是不穩(wěn)定的排序算法。相對(duì)于快速排序來說，這是堆排序的最大優(yōu)點(diǎn)。此外，堆排序僅需一個(gè)記錄大小的供交換用的輔助存儲(chǔ)空間。算法代碼：/*堆排序 實(shí)現(xiàn)，算法復(fù)雜度O(nlgn)*/#include#include/*假設(shè)節(jié)點(diǎn)i的左右子樹都是最大堆，操作使節(jié)點(diǎn)i的子樹變成最大堆*/void maxHeap(int A,int len,int i) int l,r,large,temp; l=2*i; r=2*i+1; large=i; if(lAi) large=l; if(rAlarge) large=r; if(large!=i) temp=Alarge; Alarge=Ai; Ai=temp; maxHeap(A,len,large); /*建立大根堆*/void buildMaxHeap(int A,int len) int i; for(i=len/2-1;i=0;i-) maxHeap(A,len,i);/*堆排序*/void maxHeapSort(int A,int len) int i,temp; buildMaxHeap(A,len); printf(建立大跟堆:n); for(i=0;i1;i-) temp=A0; A0=Ai-1; Ai-1=temp; printf(%-3d,Ai-1); buildMaxHeap(A,i-1); printf(n);/*測(cè)試堆排序*/int main() int i; int A11=4,11,38,23,16,98,10,14,81,78,66; printf(源序列為：n); for(i=0;i11;i+) printf(%-3d,Ai); printf(n); maxHeapSort