Python語言常用內排序算法的研究

李毅，陳巧琳，胡春兵，劉凱峰

（1.四川民族學院理工學院，四川康定 626001；2.大邑縣技工學校（成都市技師學院大邑分院），四川成都 610404）

Python語言是最近幾年來非?；鸨恼Z言。在人工智能、深度學習、模式識別、數據分析、科學計算、工業自動化、引力波探測等眾多領域，都可以看到Python語言的身影。無論是熱愛編程的中小學生，還是在探索人類知識邊界的一流科學家都在使用Python語言[2]。

隨著計算機的快速發展及應用領域的不斷擴大，由于現階段計算機硬件的速度和存儲空間比較有限，故軟件設計人員一直把提高計算機硬件速度和節省存儲空間作為重點研究方向[3]。其中，排序算法已被程序設計人員納為主要考慮的因素之一。合理的排序算法將大大提高影程序的執行效率同時減少存儲空間的占用量，甚至影響整個軟件的綜合性能。所謂數據排序，就是將一組無序的數據，按照其關鍵字的大小，遞增或遞減地排列成一個有序的序列[4]。

1 排序算法的分類

在Python語言學習過程中，經常會碰到關于字符、字符串、整數以及浮點數的排序問題。根據排序表中記錄數據量n的不同，排序過程需要的存儲空間也有所不同，故將排序算法分為外排序算法和內排序算法兩大類。外排序算法是指待排序數據量非常大，計算機的內存空間不能一次性容納全部記錄，在排序過程中需要進行數據內、外存交換[5]。內排序算法是指待排序數據在計算機隨機存儲器RAM中進行的排序過程，其過程不涉及數據的內外交換。常用的內排序算法有：希爾排序、快速排序、歸并排序、冒泡排序、簡單選擇排序、簡單插入排序等。接下來本文就通過具體的實例，對這些常用內排序算法的基本思想、執行過程、算法代碼、時間復雜度、穩定性進行逐一分析、歸納、總結。

2 部分常用內排序算法具體分析

2.1 冒泡排序

2.1.1 基本思想

冒泡排序一種典型的交換排序方法也被稱為氣泡排序，冒泡排序基本思想是數據表中無序區中相鄰元素關鍵字的比較和元素位置的交換使關鍵字較小或關鍵字較大的元素如氣泡一樣逐漸往上“漂浮”直至最終露出“水面”的過程。如此往復，最終完成排序。冒泡排序過程中，假如是對n個數進行排序，則需要進行n-1輪，每輪進行n-1-i次元素關鍵字的比較。

2.1.2 算法代碼

例：對列表R=[6,5,4,3,2,1]的元素從小到大進行排序。

該例子用冒泡算法實現代碼片段如下：

2.1.3 執行過程

每次從無序區中冒出一個關鍵字最大的元素并將其歸位。冒泡排序每輪產生的有序區是全局有序區并且有序區中的所有元素都是歸位的。初始時將全局有序區看成空，所有i從0開始排序。

2.1.4 算法分析

1最好情況分析

如果初始排序表是正序，則在第1趟排序后結束，所需要的關鍵字比較和元素移動次數均達到最小值Cmin和Mmin。

兩者合起來為O(n)，因此冒泡排序最好情況下的時間復雜O(n)。

2最壞的情況分析

若初始排序表反序，則需進行n-1趟排序，每趟排序需要進行n-i-1(0≤i≤i-2)次關鍵字的比較，3(n-i-1)次元素的移動（一次交換為3次移動）。反序時冒泡排序算法的關鍵字比較次數和元素移動次數均達到最大值Cmax和Mmax。

兩者結合起來為O(n2)，因此冒泡排序最壞情況下的時間復雜度為O(n2)。

3平均情況分析

平均情況的時間復雜度分析要稍微復雜很多，因為算法可能在中間的某一趟排序完成后就結束，但是平均的排序趟數仍是O(n)，每一趟的比較次數和元素移動次數為O(n)，所以平均時間復雜度為O(n2)。由于冒泡排序算法平均時間性能接近最壞的時間性能，故冒泡排序算法是一種低效的排序方法。

由于在冒泡排序算法中只使用了固定的幾個輔助變量，與數據規模n無關，因此算法的空間復雜度為O(1)，冒泡排序就是一個就地排序算法。對于任意兩個滿足i＜j且R[]

i=R[j]

的元素，兩者沒有逆序，不會發生交換，也就是說R[i]和R[j]的相對位置保存不變，所以冒泡排序算法是穩定排序算法。

2.2 簡單插入排序

2.2.1 簡單插入排序基本思想

在一個數據表中每次將無序區中一個待排序元素按照其關鍵字或大或小插入有序區中合適位置。先比較數據表中前兩個相鄰數據，按其關鍵字大小排序，形成有序區。接著每次從無序區中取出第一個元素，按照其關鍵字大小將其插入到有序區中最合適位置，使有序區中元素仍然保持有序，直到無序區中全部元素被插入到有序區中為止。

2.2.2 算法代碼

例：對于列表R=[66,55,44,33,22,11]的元素從小到大排列

該例子用簡單插入排序算法實現代碼片段如下：

2.2.3 執行過程

簡單插入排序每趟產生的有序區是局部有序區（初始時將R[0]看成局部有序區，所以i從1開始排序），局部有序區中的元素并不是一定放在最終位置上，在后面的排序中可能發生元素位置的改變，當一個元素在排列結束前就已經放在其最終位置上將其稱為歸位。相應地全局有序區中的所有元素均已歸位。

表2 6個元素進行簡單插入排序過程

2.2.4 算法分析

簡單插入排序是由兩重循環構成的，對于具有n個元素的順序表R，外循環表示要進行n-1趟排序。在每一趟排序中，當且僅當待插入元素R[i]小于有序區的尾元素時才進入內循環，所以簡單插入排序的時間性能與初始排序表相關。

1最好情況分析

如果初始數據表按關鍵字正序，則在每趟R[i](1≤i≤n-1)的排序中僅需進行一次比較，由于比較結果是正序，這樣每趟排序均不進入內循環，故元素移動次數為0。正序時簡單插入排序的比較次數和元素移動次數均達到最小值Cmin和Mmin。

2最壞情況分析

如果初始排序表按關鍵字反序，故在每趟R[i](1≤i≤n-1)的排序中，由于tmp均小于有序區中的所有元素，則需要i次關鍵字比較，同時有序區中的每個元素后移一位，再加上前面tmp=R[i]和R[ ]j+1=tmp的兩次移動，需要i+2次移動。由此可見，反序時簡單插入排序的比較次數和元素移動次數均達到最大值Cmax和Mmax。

兩者結合起來為O(n2)，故簡單插入排序算法最壞時間復雜度為O(n2)。

3平均情況分析

在每趟R[i](1≤i≤n-1)的排序中，平均情況是將R[i](1≤i≤n-1)插入有序區的中間位置，這樣平均比較次數為i/2，平均移動次數為i/2+2，對應的Cavg和Mavg。

兩者結合起來為O(n2)，故簡單插入排序算法平均情況下的時間復雜度為O(n2)。由于簡單插入排序算法的平均時間性能接近最壞性能，所以是一種低效的排序算法。

簡單插入排序算法中只使用了i、j和tmp共三個輔助變量，與數據規模n無關，故算法的空間復雜度為O(1)，也就是說簡單插入排序算法是一個就地排序算法。簡單插入排序算法也是穩定排序算法同冒泡排序算法一樣。

2.3 簡單選擇排序

2.3.1 基本思想

簡單選擇排序算法的基本思想是每次從無序區中選出關鍵字最小或者最大的元素，按順序排放在有序區的最后。假如從第i趟排序開始時，當有序區為R[0..i-1]，無序區為R[i..n-1](0≤i≤n-1)，則第i趟排序是從無序區中挑選出關鍵字最小或者最大的元素R[k]，并將R[k]與R[i]交換，使R[0..i]成為新的有序區R[i+1..n-1]成為新的無序區。這樣不斷擴大有序區，縮小無序區，直到全部元素有序為止。

2.3.2 代碼實現

例：對于列表R=[18,17,19,8,11,13,12,14]的元素從小到大排列

該例子用簡單選擇排序算法實現代碼片段如下：

2.3.3 執行過程

簡單選擇排序每趟產生新的有序區都是全局有序，有序區中所有元素都是歸位了。

表3 8個元素進行簡單插入排序過程

2.3.4 算法分析

無論初始排序表的順序如何，在第i趟排序中找出無序區中的最小元素，內for循環需要做n-i-1次比較，故總的比較次數為Cn。

元素移動次數，當初始排序表正序時，移動次數為0，反序時每趟排序均要執行交換操作，此時元素總的移動次數為最大值Mmax=3(n-1)。然而，無論初始排序表如何分布，所需的元素比較次數都相同，故簡單選擇排序算法的最好，最壞及平均時間復雜度均為O(n2)。同冒泡排序算法與簡單插入排序算法相比，簡單選擇排序算法中元素移動次數是最少的。

簡單選擇排序算法中只使用了固定的幾個復雜變量，與數據規模n無關，故簡單選擇排序算法與冒泡排序算法、簡單插入排序算法一樣是一個就地排序算法，空間復雜度為O(1)。另外，簡單選擇排序算法是一種不穩定的排序算法。

3 各種內排序算法的比較和選擇[6,7,8]

除了上述分析的三種常見的排序算法外，還二路歸并排序、希爾排序、堆排序、快速排序、折半插入排序等，下面對這些內排序算法進行逐一細致的總結。

表3 部分常用排序算法性能

沒有哪一種內排序算法是絕對好的，每一種內排序算法都有其優缺點，在實際應用中需要根據具體情況選擇合適的方法。

4 總結

如果待排數據表中數據規模n較小，一般使用簡單選擇排序或直接插入排序[9]。直接插入排序相比簡單插入排序具有優越性，但是直接插入排序元素移動多余簡單選擇排序。如果初始情況有序表是正序，選擇冒泡排序算法或直接插入排序算法比較合理。如果待排數據表中數據規模n較大，應該首先選用的是時間復雜度為O(nlog2n)的排序算法，如二路歸并，堆排序或者快速排序。目前內排序算法中被認為是較好的算法是快速排序，當排序表中元素的關鍵字是隨機分布時，使用快速排序用平均時間是最少的；但是快速排序所需的輔助空間要多余堆排序，堆排序不會出現快速排序可能出現的最壞的情況，同時堆排序和快速排序都是不穩定的。如果要求內排序穩定，則選擇二路歸并排序。如果要將兩個有序數據表合成一個新的有序數據表，選用二路歸并排序是非常合理的。