Python語言常用內(nèi)排序算法的研究

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

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

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

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

1 排序算法的分類

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

2 部分常用內(nèi)排序算法具體分析

2.1 冒泡排序

2.1.1 基本思想

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

2.1.2 算法代碼

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

該例子用冒泡算法實現(xiàn)代碼片段如下：

2.1.3 執(zhí)行過程

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

2.1.4 算法分析

1最好情況分析

如果初始排序表是正序，則在第1趟排序后結(jié)束，所需要的關(guān)鍵字比較和元素移動次數(shù)均達(dá)到最小值Cmin和Mmin。

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

2最壞的情況分析

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

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

3平均情況分析

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

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

i=R[j]

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

2.2 簡單插入排序

2.2.1 簡單插入排序基本思想

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

2.2.2 算法代碼

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

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

2.2.3 執(zhí)行過程

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

表2 6個元素進(jìn)行簡單插入排序過程

2.2.4 算法分析

簡單插入排序是由兩重循環(huán)構(gòu)成的，對于具有n個元素的順序表R，外循環(huán)表示要進(jìn)行n-1趟排序。在每一趟排序中，當(dāng)且僅當(dāng)待插入元素R[i]小于有序區(qū)的尾元素時才進(jìn)入內(nèi)循環(huán)，所以簡單插入排序的時間性能與初始排序表相關(guān)。

1最好情況分析

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

2最壞情況分析

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

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

3平均情況分析

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

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

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

2.3 簡單選擇排序

2.3.1 基本思想

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

2.3.2 代碼實現(xiàn)

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

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

2.3.3 執(zhí)行過程

簡單選擇排序每趟產(chǎn)生新的有序區(qū)都是全局有序，有序區(qū)中所有元素都是歸位了。

表3 8個元素進(jìn)行簡單插入排序過程

2.3.4 算法分析

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

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

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

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

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

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

沒有哪一種內(nèi)排序算法是絕對好的，每一種內(nèi)排序算法都有其優(yōu)缺點，在實際應(yīng)用中需要根據(jù)具體情況選擇合適的方法。

4 總結(jié)

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