一種提升快速排序效率的改進(jìn)算法

羅 可

（邵陽學(xué)院 圖書館，湖南 邵陽 422000）

0 引言

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

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

1 相關(guān)知識

1.1 快速排序

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

步驟1:將第1 個數(shù)據(jù)指定為鍵值(或稱基準(zhǔn)鍵,

Pivot key)。

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

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

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

1.2 算法復(fù)雜度

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

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

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

假設(shè)我們要將n個待排序的數(shù)據(jù):data［1］、data

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

時空復(fù)雜性如下。

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

最優(yōu)值:O(nlog2n)。

平均值:O(nlog2n)。

優(yōu)勢:平均執(zhí)行時間最優(yōu),算法執(zhí)行速度快。

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

2 提出新的快速排序改進(jìn)算法

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

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

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

算法:快速排序改進(jìn)算法

輸入:待排序數(shù)據(jù)和位置

輸出:已排序數(shù)據(jù)

代碼如下:

3 實驗分析與結(jié)果

3.1 實驗環(huán)境搭建

本文研究使用個人計算機一臺執(zhí)行程序,并比較標(biāo)準(zhǔn)型及改良型的快速排序法在同組數(shù)據(jù)執(zhí)行時所花費時間,其硬設(shè)備信息如下。

臺式個人計算機一部

型號:聯(lián)想

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

RAM:8.00GB；

系統(tǒng)類型:64 位操作系統(tǒng)Windows10 專業(yè)版；

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

3.2 算法實際效率測試

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

算法的執(zhí)行時間上,改進(jìn)算法在隨機生成的10 組執(zhí)行平均時間比標(biāo)準(zhǔn)類型的算法快了近20 倍,如圖1所示。 對于由隨機數(shù)產(chǎn)生的1 000 個數(shù)據(jù)進(jìn)行排序,該算法能平均加速84.6 ms。 從實驗結(jié)果中可以看出,改進(jìn)的算法能夠提高排序速度。

圖1 標(biāo)準(zhǔn)型及改良后快速排序法運行時間比較

4 結(jié)語

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

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