什麼是排序算法？

排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規範，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存；我們通常所說的排序算法往往指的是內部排序算法，即數據記錄在內存中進行排序。

插入排序

插入排序的基本操作是將一個記錄插入到已經排好的有序表中，從而得到一個新的、記錄數增1的有序表。對於給定的一組記錄，初始時假定第一個記錄自成一個有序序列，其餘記錄為無序序列。接著從第二個記錄開始，按照記錄的大小依次將當前處理的記錄插入到其之前的有序序列中，直到最後一個記錄插到有序序列中為止。

• 排序過程

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置後
6. 重複步驟2~5

• 算法實現

選擇排序

選擇排序：比如在一個長度為N的無序數組中，在第一趟遍歷N個數據，找出其中最小的數值與第一個元素交換，第二趟遍歷剩下的N-1個數據，找出其中最小的數值與第二個元素交換......第N-1趟遍歷剩下的2個數據，找出其中最小的數值與第N-1個元素交換，至此選擇排序完成。

• 排序過程

1. 由輸入的無序數組構造一個最大堆，作為初始的無序區
2. 把堆頂元素（最大值）和堆尾元素互換
3. 把堆（無序區）的尺寸縮小1，並調用heapify(A, 0)從新的堆頂元素開始進行堆調整
4. 重複步驟2，直到堆的尺寸為1

• 算法實現

交換排序

交換排序：就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置。交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

• 排序過程

1. 從序列中挑出一個元素，作為"基準"(pivot).
2. 把所有比基準值小的元素放在基準前面，所有比基準值大的元素放在基準的後面（相同的數可以到任一邊），這個稱為分區(partition)操作。
3. 對每個分區遞歸地進行步驟1~2，遞歸的結束條件是序列的大小是0或1，這時整體已經被排好序了。

• 算法實現

歸併排序

歸併排序：將待排序序列R[0...n-1]看成是n個長度為1的有序序列，將相鄰的有序表成對歸併，得到n/2個長度為2的有序表；將這些有序序列再次歸併，得到n/4個長度為4的有序序列；如此反覆進行下去，最後得到一個長度為n的有序序列。

• 排序過程

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
4. 重複步驟3直到某一指針到達序列尾
5. 將另一序列剩下的所有元素直接複製到合併序列尾

• 算法實現

基數排序

基數排序已經不再是一種常規的排序方式，它更多地像一種排序方法的應用，基數排序必須依賴於另外的排序方法。基數排序的總體思路就是將待排序數據拆分成多個關鍵字進行排序，也就是說，基數排序的實質是多關鍵字排序。

如果按照習慣思維，會先比較百位，百位大的數據大，百位相同的再比較十位，十位大的數據大；最後再比較個位。人得習慣思維是最高位優先方式。但一旦這樣，當開始比較十位時，程序還需要判斷它們的百位是否相同--這就認為地增加了難度，計算機通常會選擇最低位優先法。

基數排序方法對任一子關鍵字排序時必須藉助於另一種排序方法，而且這種排序方法必須是穩定的。對於多關鍵字拆分出來的子關鍵字，它們一定位於0-9這個可枚舉的範圍內，這個範圍不大，因此用桶式排序效率非常好。對於多關鍵字排序來說，程序將待排數據拆分成多個子關鍵字後，對子關鍵字排序既可以使用桶式排序，也可以使用任何一種穩定的排序方法。

• 算法實現

閱讀更多 咱小二 的文章

關鍵字: 算法 記錄 有序