《排序算法論》word版.docx

排序算法 姓名：鄧 海 波 學號：2013222053 年級：2013 級 專業(yè): 生物信息學1、 算法介紹排序算法是為了解決輸入的n個數(shù)的一個序列,.,經(jīng)過我們的排序后輸出已排好的序列,.,(滿足.)。我們將通過不同的排序算法解決這個問題，比如選擇排序、插入排序、冒泡排序、快速排序、堆排序、歸并排序、希爾排序、基數(shù)排序等，并通過對其時間復雜度進行對比進而得出相應的結(jié)論。2、 基本算法1、 選擇排序選擇排序的基本思想是： 對待排序的n個數(shù)據(jù)進行n-1遍的處理，第1遍處理是將a2.n中最小者與a1交換位置，第2遍處理是將a3.n中最小者與a2交換位置，.，第i遍處理是將ai+1.n中最小者與ai交換位置。這樣，經(jīng)過i遍處理之后，前i個記錄的位置就已經(jīng)按從小到大的順序排列好了?？偣脖容^ n(n-1)/2 次，時間復雜度為(),其穩(wěn)定性為不穩(wěn)定（穩(wěn)定性是指值相同的數(shù)字在排序前后其相對位置是否要發(fā)生改變，若要改變就是不穩(wěn)定，否則就是穩(wěn)定的。）算法代碼： main() int flag,temp,i,j,a10=12,33,45,67,89,99,45,11,22,48; printf(源程序為：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、 冒泡排序冒泡排序基本思想是:對待排序的數(shù)字進行兩兩比較,如發(fā)現(xiàn)兩個數(shù)字是反序的,則進行交換,直到無反序的記錄為止（此處是按從大到小的順序排列）?？偣脖容^ n(n-1)/2 次，時間復雜度為(),是穩(wěn)定的排序算法。算法代碼：main() int i,j,l,a10=9,89,90,23,56,12,45,67,36,99; printf(源程序為：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、 插入排序有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法-插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復雜度為()。是穩(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、 快速排序思想：每次找一個數(shù)位基準，把小于等于它的放到這個數(shù)的左邊，把大于等于它的放到它的右邊，每排完一趟，小于等于基準值的，在其左側(cè)。大于等于基準值的在其右側(cè)。平均時間復雜度：()是不穩(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(源程序為：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個元素的序列,.,，當&時我們稱為最小化堆或小頂堆，當&時我們稱為最大化堆或大頂堆(i=1,2,.,n)。由此，若序列,.,是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。若在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列，這個過程稱之為堆排序。排序過程：堆排序是一種選擇排序。建立的初始堆為初始的無序區(qū)。排序開始，首先輸出堆頂元素（因為它是最值），將堆頂元素和最后一個元素交換，這樣，第n個位置（即最后一個位置）作為有序區(qū)，前n-1個位置仍是無序區(qū)，對無序區(qū)進行調(diào)整，得到堆之后，再交換堆頂和最后一個元素，這樣有序區(qū)長度變?yōu)?，不斷進行此操作，將剩下的元素重新調(diào)整為堆，然后輸出堆頂元素到有序區(qū)。每次交換都導致無序區(qū)-1，有序區(qū)+1。不斷重復此過程直到有序區(qū)長度增長為n-1，排序完成。想得到升序，則建立大頂堆，若想得到降序，則建立小頂堆。堆排序在最壞的情況下，其時間復雜度：()是不穩(wěn)定的排序算法。相對于快速排序來說，這是堆排序的最大優(yōu)點。此外，堆排序僅需一個記錄大小的供交換用的輔助存儲空間。算法代碼：/*堆排序 實現(xiàn)，算法復雜度O(nlgn)*/#include#include/*假設節(jié)點i的左右子樹都是最大堆，操作使節(jié)點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);/*測試堆排序*/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