幾種常見排序算法的分析

泡排序是最簡單的排序算法，在所有算法中平均效率是最低的，但便于理解，適用于記錄個數ｎ較小的排序中；選擇排序適用于記錄個數ｎ較小而記錄本身信息量較大的排序中；插入排序適用于記錄個數ｎ較小而原數組基本有序的排序中；希爾排序適用于記錄個數較大而記錄本身信息量較小的排序中；快速排序是從平均時間性能而言最佳的算法，適用于記錄個數ｎ較大而記錄無序的排序中；歸并排序適用于記錄個數ｎ較大而記錄信息量也較大的排序中；基數排序適合于ｎ值很大而關鍵字較小的序列。

排序算法概述

排序定義: 所謂計算機中的排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。而排序算法(Sortingalgorithm)則是一種能將一串數據依照特定的方式進行排列的一種算法。

排序方式: 利用所需重排記錄的排序碼(SortKey)的值的大小，按照升序或降序將原紀錄的順序重新安排。

插入排序算法介紹

插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。插入排序的算法思路：
（1） 設置監視哨r[0]，將待插入紀錄的值賦值給r[0]；
（2） 設置開始查找的位置j；
（3） 在數組中進行搜索，搜索中將第j個紀錄后移，直至r[0].key≥r[j].key為止；
（4） 將r[0]插入r[j+1]的位置上。

如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間復雜度為O(n^2）。因而，插入排序不適合對于數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。

希爾排序算法介紹

先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2 < d1重復上述的分組和排序，直至所取的增量d_t=1(d_t < d_(t-1) < ? < d_2 < d_1)，即所有記錄放在同一組中進行直接插入排序為止。
該方法實質上是一種分組插入方法。
比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比[2] 較就可能消除多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。

冒泡排序算法介紹

假如一個數組有n個數，那么我們可以從第一個數開始從頭到尾兩兩比較，當前一個數比后一個數大時，則交換他們的位置，直到最大的一個數被排在了數組的后尾。然后最后一個數固定，不再需要比較，只需要按照剛剛的方法重復比較前面的n-1個數，知道排出順序。

快速排序算法介紹

快速排序（Quicksort）是對冒泡排序的一種改進。
它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一趟快速排序。

算法是：
1）設置兩個變量I、J，排序開始的時候：I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；
3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個小于key的值A[J]，并與key交換；
4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個大于key的A[I]，與key交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最后另循環結束。)

選擇排序算法介紹

選擇排序的基本思想：第1趟，在待排序記錄r[1]~r[n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2]~r[n]中選出最小的記錄，將它與r[2]交換；以此類推，第i趟在待排序記錄r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

歸并排序算法介紹

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

基數排序算法介紹

基數排序與本系列前面講解的七種排序方法都不同，它不需要比較關鍵字的大小。
它是根據關鍵字中各位的值，通過對排序的N個元素進行若干趟“分配”與“收集”來實現排序的。

不妨通過一個具體的實例來展示一下，基數排序是如何進行的。 設有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。我們知道，任何一個阿拉伯數，它的各個位數上的基數都是以0~9來表示的。所以我們不妨把0~9視為10個桶。
我們先根據序列的個位數的數字來進行分類，將其分到指定的桶中。例如：R[0] = 50，個位數上是0，將這個數存入編號為0的桶中。（如圖1）

圖1 基數排序

分類后，我們在從各個桶中，將這些數按照從編號0到編號9的順序依次將所有數取出來。
這時，得到的序列就是個位數上呈遞增趨勢的序列。
按照個位數排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下來，可以對十位數、百位數也按照這種方法進行排序，最后就能得到排序完成的序列。