一種提升快速排序效率的改進算法

羅 可

（邵陽學院 圖書館，湖南 邵陽 422000）

0 引言

在人類各個領域中,數據排序得到了廣泛的應用,幾乎每一個地方都需要進行數據排序。 經過排序的數據,優點如下:(1)更易讀,更易觀察。 (2)數據有利于再進一步進行各種統計和整理工作,例如,要確定一組數據的中位數,必須先對數據進行排序,然后才能得出結果。 (3)排序后的數據可大大縮短搜索數據的時間。

隨著數據排序技術的不斷發展,各種排序算法相繼出現。 常用的方法有選擇排序法(Selection Sort)、冒泡排序法(Bubble Sort)、插入排序法(Insertion Sort)、希爾排序法(Shell Sort)、快速排序法(Quick Sort)等。 每一種排序算法都有其自身的特點,而且算法有簡單和復雜之分。 通常簡單的排序算法完成排序的速度較慢,即排序效率較低；復雜的排序算法完成排序的速度較快,排序效率較高。 一般來說,在目前眾多的排序方法中,快速排序法(Quick Sort)是一種速度較快的排序算法,有關文獻對其進行了大量的論述。 快速排序法的操作原理是在所有數據中選擇一個基準鍵(Pivot),然后利用分割(Partition)方法將數據分成兩半,然后再對這兩部分進行分割,直到完成排序。 執行快速排序法所需的時間取決于對基準鍵(Pivot)的選擇,同時還建議了許多選擇方法,其中大部分的改進方法都是圍繞對基準鍵(Pivot)的選擇展開的。 本文探討的是改進分割(Partition)算法,通過這種方法能否提高快速排序法的運行時間。

1 相關知識

1.1 快速排序

［2］……data［n］,由小至大排序,其步驟如下。

步驟1:將第1 個數據指定為鍵值(或稱基準鍵,

Pivot key)。

步驟2:利用指標i 自左而右找到1 個data［i］＞＝pivotkey；利用指標j 自右而左找到1 個data［j］＜pivot key,若i＜j則對換data［i］、data［j］。

步驟3:并繼續執行步驟2,否則對換Pivot(即data［1］)、data［j］,此時數組被分成2 部分data［1］、data［2］、data［3］……、data［j］、data［j+1］、data［j+2］……、data［n］。

在這些數據中,data［j］(也就是最初的pivot)的左邊所有數據都小于data［j］；data［j］右邊所有數據都大于data［j］,而data［j］在整個數組中的位置,也就是排序之后的位置。 再按照上述步驟對data［j］的左右兩個數組繼續執行,直到每一部分只剩下1 個數據,也就是完成了所有數據的增量排序。

1.2 算法復雜度

算法優劣取決于其時間復雜性T(n)和空間復雜性S(n),而排序算法(見表1)也是如此。 時間復雜性是指算法在運行過程中所花費的時間,而空間復雜性則是在運行過程中所占用的存儲空間的單位長度。 當前,很多學者都是從理論上對不同的排序算法進行性能分析［2-5］。

表1 各種常見排序算法之比較

快速排序法［1］(Quick Sort)又稱為劃分交換排序法(Partition-exchange sort),是利用分治法(Divide and conquer)方式,把要排序的數組分成幾個小的部分,然后繼續對小的部分進行處理,最后形成每一個處理過的小部分,從而得到一個良好的排序結果。

假設我們要將n個待排序的數據:data［1］、data

快速排序法的特征分析如下:作為分治法的一種應用,依靠連續的(Partition)數組分割來達到排序的目的,程序通常都是通過遞歸的方式來實現的。

時空復雜性如下。

最差情況:O(n2),發生在Pivot key＝data［1］,而且數組已排序完成,此時將退化為冒泡排序法。

最優值:O(nlog2n)。

平均值:O(nlog2n)。

優勢:平均執行時間最優,算法執行速度快。

不足:需要額外的空間來處理排序。

2 提出新的快速排序改進算法

除Pivot之外,每個數組值在快速排序法分割過程中都會被處理一次,并且處理程序可能只是將數組值與Pivot比較,也可能需要對換Pivot和數組值,這是一個最耗時但又不可避免的程序。 所以,如果在這個過程中,用來同時找到數組的最小和最大值的話,那么每一次(Pass)完成排序定位的數組的值,從最初的1(即Pivot)增加到3(Pivot),即Pivot、最小值和最大值,從而提高了算法的效率。

改進的快速排序方法主要應用于(Partition)分割部分,首先將數組值的最大和最小值都設置為Pivot,然后在尋找比Pivot更大的數組索引i時,如果它比當前數組值的最小值更小,則將其改為當前數組值。 同樣,查找比Pivot小的數組索引j時,如果該數組的最大值大于當前數組值,則將其改為當前數組的最大值。

如果i＞j表明所有數組都搜索過一次,則該數組的最大值和最小值也可以確定,這樣,在經過一次(Pass)之后,就可以確定Pivot、最大值和最小值,再將第一個(Pass)值和最小值交換,最后一個(Pass)值和最大值交換,然后傳遞到下一次(Pass)數組總數,這樣就比原來的算法少了2 個(Pass)值。

算法:快速排序改進算法

輸入:待排序數據和位置

輸出:已排序數據

代碼如下:

3 實驗分析與結果

3.1 實驗環境搭建

本文研究使用個人計算機一臺執行程序,并比較標準型及改良型的快速排序法在同組數據執行時所花費時間,其硬設備信息如下。

臺式個人計算機一部

型號:聯想

CPU:Intel(R)Pentium(R)G3250@3.20GHz；

RAM:8.00GB；

系統類型:64 位操作系統Windows10 專業版；

使用軟件:Python3.8 版、Microsoft Excel2007 版。

3.2 算法實際效率測試

首先,利用Python程序語言的隨機數函數,自動生成10 000 個隨機數據,數值大小為0 到9 999 之間,每組取出1 000 個,總共重復取出100 組,然后分別寫到列表中,作為測試標準型和改進算法運行時間的數據源。 下一步,讀取第一組1 000 個數據,使用一個標準類型的快速排序算法,對它們進行由小到大的排序,并記錄其運行時間以便于觀察,這樣重復直到100 組數據完成排序。 如前所述,通過使用改進的快速排序法程序讀取每次100 組時間,然后將其平均時間寫到Excel表格中。 對以上兩種排序方法的運行時間進行比較分析,得出相應的結論。

算法的執行時間上,改進算法在隨機生成的10 組執行平均時間比標準類型的算法快了近20 倍,如圖1所示。 對于由隨機數產生的1 000 個數據進行排序,該算法能平均加速84.6 ms。 從實驗結果中可以看出,改進的算法能夠提高排序速度。

圖1 標準型及改良后快速排序法運行時間比較

4 結語

本文改進了快速排序法的分割步驟。 每一步生成3 個位置:Pivot,Minimum,Minimum,改進了傳統的快速排序法,并用Python語言進行了驗證。 通過實驗,在同一電腦上對100 組由計算機隨機數生成的數據進行了排序對比,大多數情況下,本文算法減少了完成排序所需的時間。 隨著計算機處理速度不斷提高,在大多數情況下,處理大量的數據已經不像以前那樣需要很長時間才能得到結果,但對于更好的東西和更好的結果的追求,是人們長久以來所遵循的一種行為方式。

本文的實證結果初步達到了這一目的,期望能起到拋磚引玉的作用,讓更多有興趣從事這一領域研究和探索的學者參與這一領域,使更多的排序算法更趨完善。