# 排序算法 很多計算機科學家認為排序是算法研究中的最基礎問題。這里將介紹幾種排序算法并給出偽代碼，及其運行時間分析。 ## 1.選擇排序 假設有一系列數A,首先從序列A中找出一個最小數，并把它放在第一個數的位置，原來第一個數就放在最小數的位置。接下來，從剩余的數中找出最小數，交換位置---如此下去，當執行到倒數第二個數時，序列A就排好序（升序）。 先說下偽代碼：A代表數組，下標從1到它的長度A.length;方法，條件，循環用空格隔開表示一個塊結構；為什么用偽代碼？我們寫程序時不能局限于一種語言，并且偽代碼能很容易被人看懂，只要有些寫代碼的經驗的人呢就能看懂。 ~~~ choose_sort(A) 代價 次數 n=A.length c1 1 for i=1 to n-1 c2 n min = A[i] c3 n-1 m=1 c4 n-1 for j=i+1 to n c5 (2+n)(n-1)/2 if A[j]<min c6 n(n-1)/2 min=A[i] c7 m=j c8 temp=A[i] c9 n-1 A[i]=min c10 n-1 A[m]=temp c11 n-1 ~~~ 接下來，分析算法的運行時間： 對于一臺特定的機器，算法中的每一步花費的時間都是一定。我們主要考慮每一步的執行次數。 如上所示，某些步驟的運行次數一定。對于長度為n的序列,如果序列剛好升序排好了，那么c7，c8的次數均為0； 如果序列剛好是降序排好了，那么c7,c8的次數均為你（n-1)/2，但這里我們只考慮最壞情況，這樣就能使我們的運行時間更具說服力 總代價：（c5+c6+c7+c8)*n^2/2+(c2+c3+c4+c9+c9+c10+c11+c5-c6/2-c7/2-c8/2)*n+c1-(3/2)*c5-c3-c4，即a*n^2+b*n+c 由于對于一臺機器代價一定，于是a,b,c是確定的，所以運行時間只有輸入規模n所確定；當n很大很大時以至于n＾2的系數，和低階的項對于結果影響不大，就可以舍棄ａ和低階項 因此，改算法的運行時間只有ｎ^2決定，表示為O(n^2) ## 2.插入排序 一個已排好序的序列，我們可以把一個數插入到某個位置，使其序列升序排列。 一系列的數，我們可以以第一個數開始插入排序，因為一個數根本不用考慮排序問題 ~~~ insert_sort(A) n=A.length for i=2 to n for j=i-1 to 1 if A[j+1]<A[j] temp=A[j] A[j]=A[j+1] A[j+1]=temp ~~~ 時間復雜度為O(n^2) ## 3.冒泡排序 。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。 ~~~ bubble_sort(A) n=A.length a=true while a a=false for i=1 to n-1 if A[i]>A[I+1] a=true temp=A[i+1] A[i+1]=A[i] A[i]=temp 時間復雜度為O(n^2) ~~~ ## 4.歸并排序 這里先介紹下分治法：就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 將一系列數進行分割，每一次分割為原來的一半，直到分割后的部分只有一個數或沒有為止；最后分割后形成的每一部分均可視為一個排好的序列，可以把這些小序列排序 怎么把兩個排序好的序列，合并為一個排序好的序列？把兩個序列的最小數進行比較，每一次取出最小數，直到兩個序列中不存在數 ~~~ merge_sort(A,p,r) if p<r q=Floor(p+r)/2 向下取整 merge_sort(A,p,q) merge_sort(A,q+1,r) merge(A,p,q,r) merge(A,p,q,r) n1=q-p+1 n2=r-p new arrays L[n1+1]andR[n2+1] for i=1 to n1 L[i]=A[p+i-1] for j=1 to n2 R[j]=A[q+j] L[n1+1]=∞ R[n2+1]=∞ i=1 j=1 for k=p to r if L[i]<=R[j] A[k]=L[i] i=i+1 else A[k]=R[j] j=j+1 ~~~ 歸并排序想要算出它的時間較困難，但是不是無法計算時間復雜度為O(n*log2(n)) 通過上面四種算法的比較，發現1 2 3 的時間復雜度相同，利用函數的性質，4的時間明顯優于其他三種 排序的算法還有很多，比如堆排序，快速排序，以后再一一分析