七、排序算法

一、排序的概念與分類

排序的一般定義

 排序是計算機內經常進行的一種操作 ， 其目的是將一組“ 無序” 的數據元素調整為“ 有序” 的數據元素。

例如 ： 將下列關鍵字序列
52, 49, 80, 36, 14, 58, 61, 23, 97, 75
調整為
14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

排序的數學定義
 假設含有n個數據元素的序列為{R1 , R2 , …, Rn },其相應的關鍵字序列為{ K1 , K2 , …, Kn }，這些關鍵字相互之間可以進行比較 ， 即在它們之間存在著這樣一個關系：
Kp1 <= Kp2 <= …<=Kpn
按此固有關系將上式記錄序列重新排列為
{ R p1 , R p2 , … ，R pn }
的操作稱作 排序 。
排序的穩定性
如果在序列中有兩個數據元素r[i]和r[j]，它們的關鍵字k[i ] ==k[j]，且在排序之前，對象r[i]排在r[j]。 如果在排序之后 ， 對象r[i]仍在對象r[j]的前面， 則稱這個排序方法是穩定的。
多關鍵字排序

排序時需要比較的關鍵字多余一個
排序結果首先按關鍵字 1 進行排序
當關鍵字 1 相同時按關鍵字 2 進行排序
……
當關鍵字 n-1 相同時按關鍵字 n 進行排序

排序中的關鍵操作

比較：任意兩個數據元素通過比較操作確定先后次序
交換： 數據元素之間需要交換才能得到預期結果

內排序和外排序

內排序：整個排序過程不需要訪問外存便能完成
外排序：待排序的數據元素數量很大 ， 整個序列的排序過程不可能在內存中完成

排序的審判

時間性能：關鍵性能差異體現在比較和交換的數量
輔助存儲空間：為完成排序操作需要的額外的存儲空間；必要時可以“ 空間換時間”
算法的實現復雜性：過于復雜的排序法會影響代碼的可讀性和可維護性 ， 也可能影響排序的性能

二、基本的排序算法

選擇排序
每一趟 ( 例如第i趟 ， i = 0, 1, … , n- 2)在后面n-i 個待排的數據元素中選出關鍵字最小的元素 , 作為有序元素序列的第 i 個元素。

插入排序
當插入第i(i>=1)個數據元素時，前面的V[0], V[1], … , V[i-1]已經排好序 。 這時 ,用 V[i]的關鍵字與 V[i-1], V[i-2], … 的關鍵字進行比較 , 找到插入位置即將 V[i]插入 , 原來位置上的對象向后順移。

冒泡排序
設待排數據元素序列中的元素個數為 n。最多作 n-1趟，i = 1, 2, … … , n-1。在第 i 趟中從后向前， j = n-1, n-2, … … , i， 兩兩比較 V[j-1] 和 V[j]的關鍵字。如果發生逆序， 則交換 V[j-1] 和 V[j]。

希爾排序
將待排序列劃分為若干組，在每一組內進行插入排序，以使整個序列基本有序，然后再對整個序列進行插入排序。

將n個數據元素分為d個子序列：
{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}
{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}
...
{R[d]，R[2+d]，R[3+2d]，…，R[(k+1)d]}

其中,d稱為增量，它的值在排序過程中從大到小逐漸縮小,直至最后一趟排序減為1.

快速排序
1) 任取待排序序列中的某個數據元素( 例如： 第一個元素) 作為基準, , 按照該元素的關鍵字大小將整個序列劃分為左右兩個子序列：
 左側子序列中所有元素都小于或等于基準元素
 右側子序列中所有元素都大于基準元素
 基準元素排在這兩個子序列中間
2) 分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止 。

歸并排序
將兩個或兩個以上的有序序列合并成一個新的有序序列
V[1] … V[m]和V[ m +1] … V[n] -------------------> V[1] … V[n]
這種歸并方法稱為2路歸并。

總結：
希爾排序 ， 快速排序和歸并排序將排序算法的時間復雜度提高到了 O(n*logn)
希爾排序和快速排序的排序結果是不穩定的
算法實現源碼