羅 可

（邵陽(yáng)學(xué)院 圖書(shū)館，湖南 邵陽(yáng) 422000）

0 引言

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

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

1 相關(guān)知識(shí)

1.1 快速排序

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

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

Pivot key)。

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

步驟3:并繼續(xù)執(zhí)行步驟2,否則對(duì)換Pivot(即data［1］)、data［j］,此時(shí)數(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］在整個(gè)數(shù)組中的位置,也就是排序之后的位置。 再按照上述步驟對(duì)data［j］的左右兩個(gè)數(shù)組繼續(xù)執(zhí)行,直到每一部分只剩下1 個(gè)數(shù)據(jù),也就是完成了所有數(shù)據(jù)的增量排序。

1.2 算法復(fù)雜度

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

表1 各種常見(jiàn)排序算法之比較

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

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

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

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

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

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

平均值:O(nlog2n)。

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

不足:需要額外的空間來(lái)處理排序。

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

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

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

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

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

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

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

代碼如下:

3 實(shí)驗(yàn)分析與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境搭建

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

臺(tái)式個(gè)人計(jì)算機(jī)一部

型號(hào):聯(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 算法實(shí)際效率測(cè)試

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

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

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

4 結(jié)語(yǔ)

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

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