[科普中國]-排序算法

所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面。一個優(yōu)秀的算法可以節(jié)省大量的資源。在各個領(lǐng)域中考慮到數(shù)據(jù)的各種限制和規(guī)范，要得到一個符合實際的優(yōu)秀算法，得經(jīng)過大量的推理和分析。

概述所謂排序算法，即通過特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計算，大大提高了計算效率。對于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個相同的元素同時出現(xiàn)在某個序列之中，則經(jīng)過一定的排序算法之后，兩者在排序前后的相對位置不發(fā)生變化。換言之，即便是兩個完全相同的元素，它們在排序過程中也是各有區(qū)別的，不允許混淆不清。1

分類排序(Sorting) 是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個關(guān)鍵字有序的序列。

排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在算法中有8中基本排序：

(1)冒泡排序；

(2)選擇排序；

(3)插入排序；

(4)希爾排序；

(5)歸并排序；

(6)快速排序；

(7)基數(shù)排序；

(8)堆排序。

評價標(biāo)準(zhǔn)穩(wěn)定性是一個特別重要的評估標(biāo)準(zhǔn)。穩(wěn)定的算法在排序的過程中不會改變元素彼此的位置的相對次序，反之不穩(wěn)定的排序算法經(jīng)常會改變這個次序，這是我們不愿意看到的。我們在使用排序算法或者選擇排序算法時，更希望這個次序不會改變，更加穩(wěn)定，所以排序算法的穩(wěn)定性，是一個特別重要的參數(shù)衡量指標(biāo)依據(jù)。就如同空間復(fù)雜度和時間復(fù)雜度一樣，有時候甚至比時間復(fù)雜度、空間復(fù)雜度更重要一些。所以往往評價一個排序算法的好壞往往可以從下邊幾個方面入手：

（1）時間復(fù)雜度：即從序列的初始狀態(tài)到經(jīng)過排序算法的變換移位等操作變到最終排序好的結(jié)果狀態(tài)的過程所花費的時間度量。

（2）空間復(fù)雜度：就是從序列的初始狀態(tài)經(jīng)過排序移位變換的過程一直到最終的狀態(tài)所花費的空間開銷。

（3）使用場景：排序算法有很多，不同種類的排序算法適合不同種類的情景，可能有時候需要節(jié)省空間對時間要求沒那么多，反之，有時候則是希望多考慮一些時間，對空間要求沒那么高，總之一般都會必須從某一方面做出抉擇。

（4）穩(wěn)定性：穩(wěn)定性是不管考慮時間和空間必須要考慮的問題，往往也是非常重要的影響選擇的因素。2

常見排序算法插入排序插入排序算法是基于某序列已經(jīng)有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執(zhí)行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大于該最大元素，則可直接插入最大元素的后面即可，否則再向前一位比較查找直至找到應(yīng)該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，尋找最適當(dāng)?shù)奈恢?，直至全部記錄插入完畢。?zhí)行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的后面，因此插入該元素后并未改變原序列的前后順序。我們認(rèn)為插入排序也是一種穩(wěn)定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。1

冒泡排序冒泡排序算法是把較小的元素往前調(diào)或者把較大的元素往后調(diào)。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據(jù)比較結(jié)果和算法規(guī)則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關(guān)鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關(guān)鍵字進行比較，依次類推，重復(fù)進行上述計算，直至完成第(n一1)個和第n個記錄的關(guān)鍵字之間的比較，此后，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當(dāng)相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴(yán)格的穩(wěn)定排序算法，它不改變序列中相同元素之間的相對位置關(guān)系。1

選擇排序選擇排序算法的基本思路是為每一個位置選擇當(dāng)前最小的元素。選擇排序的基本思想是，基于直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩余元素中選擇最小的給該位置即可；以此類推，重復(fù)進行“最小元素”的選擇，直至完成第(n-1)個位置的元素選擇，則第廳個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同于冒泡法的細(xì)節(jié)。舉例說明：序列58539．我們知道第一遍選擇第1個元素“5”會和元素“3”交換，那么原序列中的兩個相同元素“5”之間的前后相對順序就發(fā)生了改變。因此，我們說選擇排序不是穩(wěn)定的排序算法，它在計算過程中會破壞穩(wěn)定性。1

快速排序快速排序的基本思想是:通過一趟排序算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根據(jù)該種方法對劃分后的這兩塊序列的元素分別再次實行快速排序算法，排序?qū)崿F(xiàn)的整個過程可以是遞歸的來進行調(diào)用，最終能夠?qū)崿F(xiàn)將所需排序的無序序列元素變?yōu)橐粋€有序的序列。3

歸并排序歸并排序算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規(guī)則進行排序為長序列。歸并排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合并得到n/2個長度為2(當(dāng)凡為奇數(shù)時會出現(xiàn)長度為l的情況)的有序子序列；將上述步驟重復(fù)操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該算法不會破壞序列的穩(wěn)定性，即歸并排序也是穩(wěn)定的排序算法。1

本詞條內(nèi)容貢獻者為:

馬學(xué)彬 - 副教授 - 內(nèi)蒙古大學(xué)