快速排序教學(xué)探討

應(yīng)沈靜 方奇 陶駿 馬利祥

摘?要：介紹了快速排序的概念;分析了傳統(tǒng)快速排序的弊端，遞歸深度較大會(huì)導(dǎo)致算法效率低下;提出了一種基于關(guān)鍵值為序列平均值的快速排序算法，闡述了算法的詳細(xì)運(yùn)行過程，并分析了其優(yōu)勢;通過實(shí)驗(yàn)驗(yàn)證了基于關(guān)鍵值為序列平均值的快速排序算法性能優(yōu)越。

關(guān)鍵詞：快速排序;遞歸;關(guān)鍵值;平均值

中圖分類號(hào)：TP312?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：This paper introduces the concept of fast sorting，analyses the disadvantages of traditional fast sorting，and points out that the recursive depth will lead to inefficiency of the algorithm.A fast sorting algorithm based on the average value of the pivot is proposed.The detailed operation process of the algorithm is described and its advantages are analyzed.Experiments show that the fast sorting algorithm based on the sequence average of the pivot has superior performance.

Key words：quick sort;recursion;pivot;average value

快速排序算法是一種優(yōu)秀的排序算法，它的平均時(shí)間復(fù)雜度為O（n*log2n），與冒泡排序和插入排序相比較而言，已經(jīng)有了很大的提高，n指待排序數(shù)據(jù)的規(guī)模，n越大，快速排序的優(yōu)勢越明顯[1]。

快速排序的過程第一步是選擇一個(gè)關(guān)鍵值，將排序序列進(jìn)行劃分，分成兩個(gè)子序列，然后對(duì)這兩個(gè)子序列再執(zhí)行遞歸的快速排序，直至子序列中只含有一個(gè)元素為止。由此可見，選擇關(guān)鍵值至關(guān)重要，關(guān)鍵值不同會(huì)導(dǎo)致劃分的子序列的規(guī)模不同，這將嚴(yán)重影響快速算法的效率[2]。

傳統(tǒng)的快速排序算法一般都會(huì)選擇排序序列的第一個(gè)元素作為關(guān)鍵值，如果此時(shí)待排序序列已經(jīng)基本有序，則選擇第一個(gè)元素作為關(guān)鍵值會(huì)使遞歸的層次達(dá)到最大，增加了算法的時(shí)間復(fù)雜度。本文提出了基于關(guān)鍵值為序列平均值的快速排序算法，其以排序序列的平均值作為關(guān)鍵值，這會(huì)使遞歸的層次達(dá)到最小，使快速算法的效率更優(yōu)[3]。

1 傳統(tǒng)的快速排序算法

這個(gè)過程稱為劃分，劃分算法的偽代碼如表1所示：

在序列劃分執(zhí)行完之后，要對(duì)兩個(gè)子序列進(jìn)行快速排序，這里的關(guān)鍵是計(jì)算出兩個(gè)子序列的開始和結(jié)束位置，然后進(jìn)行遞歸的快速排序，其對(duì)應(yīng)的快速排序算法偽代碼如表2所示：

這種算法的缺點(diǎn)在于，當(dāng)需要排列的序列元素基本有序時(shí)，遞歸的層次偏高，影響算法效率。設(shè)快速排序算法對(duì)應(yīng)的函數(shù)的名稱為qsort（序列，序列首元素位置，序列末元素位置），則對(duì)一個(gè)需要升序排列的序列a[]={1，2，3，4，5，6，7}執(zhí)行快速排序的執(zhí)行過程qsort（a，0，6）如圖1所示：

圖1中遞歸調(diào)用的深度為6，如果有n個(gè)元素，則對(duì)應(yīng)遞歸深度為n-1，算法的時(shí)間復(fù)雜度為O（n2），此時(shí)快速排序的效率達(dá)到了最差[4]。

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

傳統(tǒng)快速排序算法在序列基本有序的情況下效率較差，這是由于關(guān)鍵值選擇不合理而導(dǎo)致的，因?yàn)槭自夭⒉荒馨岩粋€(gè)序列劃分成兩個(gè)大致相等的子序列，而采取序列平均值作為關(guān)鍵值進(jìn)行劃分，效果會(huì)優(yōu)越得多[5]。

采取序列平均值作為關(guān)鍵值進(jìn)行劃分，也需要求得劃分的位置，劃分的算法和傳統(tǒng)的快速排序算法相似，但也有不同，這不同之處就在于：序列平均值并不一定會(huì)出現(xiàn)在序列中，所以得到的兩個(gè)子序列的位置計(jì)算需要額外的進(jìn)行處理[6]。

比如對(duì)于序列{1，2，3，4，6}，其平均值為3.2，按照劃分算法得到返回的位置值為2，也就是值3對(duì)應(yīng)的位置，具體的過程如圖2，共有5步：

很明顯此時(shí)3.2并不是序列的元素之一，所以其劃分的子序列不是{1，2}和{4，6}了，而是{1，2，3}和{4，6}。

對(duì)于序列{6，2，3，4，1}，其平均值為3.2，按照劃分算法得到返回的位置值為3，也就是值4對(duì)應(yīng)的位置，具體的過程如圖3，共有7步：

很明顯此時(shí)3.2并不是序列的元素之一，所以其劃分的子序列不是{1，2}和{4，6}了，而是{1，2，3}和{4，6}。

如果序列平均值恰好出現(xiàn)在序列中，則跟傳統(tǒng)的快速排序算法相似。

劃分好子序列后，再對(duì)子序列進(jìn)行遞歸的快速排序即可，劃分算法的偽代碼如表3，和傳統(tǒng)算法的劃分類似，只有pivot值進(jìn)行了修改，這里pivot值等于序列的平均值。

新快速排序算法偽代碼如表3所示：

這種算法即便是對(duì)一個(gè)基本有序的序列進(jìn)行排序，也能得到較好的效果。假設(shè)新快速排序算法對(duì)應(yīng)的函數(shù)的名稱為nqsort，那么對(duì)圖1的序列進(jìn)行快速排序的過程nqsort（a，0，6）如圖4所示：

圖4中遞歸調(diào)用的深度為3，如果有n個(gè)元素，則對(duì)應(yīng)遞歸深度約等于log2n，算法的時(shí)間復(fù)雜度為O（n*log2n），此時(shí)快速排序的效率得到了改善[8]。

3 實(shí)驗(yàn)分析

由圖5可見，排序元素個(gè)數(shù)越多，改進(jìn)的快速排序算法的優(yōu)勢也就越明顯，對(duì)于2000個(gè)元素的排序序列，平均時(shí)間優(yōu)化率已經(jīng)超出6%[9]。

4 結(jié)論

快速排序是一種用遞歸實(shí)現(xiàn)的排序方法，關(guān)鍵在于對(duì)排序序列的劃分，劃分的子序列不同，算法的效率就會(huì)有很大的不同，本文所闡述的快速排序算法，沒有使用序列首元素充當(dāng)關(guān)鍵值，而是采用了序列平均值充當(dāng)關(guān)鍵值，這會(huì)減少遞歸的深度，減低算法的時(shí)間復(fù)雜度[10]。

采用了序列平均值充當(dāng)關(guān)鍵值的快速排序算法也有其不足之處，例如對(duì)于序列{1，2，3，4，5，10000}這樣的序列進(jìn)行以序列平均值充當(dāng)關(guān)鍵值的快速排序，遞歸深度也會(huì)較大，下一步的算法改進(jìn)方向是采用序列中位數(shù)對(duì)應(yīng)數(shù)值作為關(guān)鍵值對(duì)序列進(jìn)行快速排序[11]。

參考文獻(xiàn)：

[1]秦玉平，馬靖善.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]（第3版）.北京：清華大學(xué)出版社，2015.

[2]石嵩，李宏亮，朱巍.陣列眾核處理器上的高效歸并排序算法[J].計(jì)算機(jī)研究與發(fā)展，2016，53（2）：362-373.

[3]馬靖善，秦玉平.一種改進(jìn)的歸并排序算法[J].渤海大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，30（2）：190-192.

[4]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2001.

[5]施伯樂.數(shù)據(jù)結(jié)構(gòu)教程[M].上海：復(fù)旦大學(xué)出版社，2011.

[6]林建秋，韓靜萍.C語言程序設(shè)計(jì)[M].北京：機(jī)械工業(yè)出版社，2014.

[7]嚴(yán)煒煒.科研合作中的信息需求結(jié)構(gòu)與協(xié)同信息行為[J].情報(bào)科學(xué)，2016，34（12）：11-16.

[8]衛(wèi)星，張建軍，石雷，等.云計(jì)算數(shù)據(jù)中心服務(wù)器數(shù)量動(dòng)態(tài)配置策略[J].2015，37（08）：2007-2013.

[9]左建安，陳雅.大數(shù)據(jù)時(shí)代的科學(xué)數(shù)據(jù)共享模式研究[J].新世紀(jì)圖書館，2014（03）：32-35.

[10]顏云生，陶駿.基于AHP算法的電子書包評(píng)估系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)與應(yīng)用，2017（8）：49-54.

[11]王瑞娜.基于嵌入式Linux的智能家居系統(tǒng)的研究與設(shè)計(jì)[J].廊坊師范學(xué)院學(xué)報(bào)，2017（17）：34-38.

基金項(xiàng)目：安徽省教育廳質(zhì)量工程項(xiàng)目（2017jxtd145），安徽省科技廳重點(diǎn)研究與開發(fā)計(jì)劃項(xiàng)目（201904a05020093），蕪湖市科技項(xiàng)目（2019yf49）

作者簡介：應(yīng)沈靜（2000—?），女，浙江麗水人，本科，主要研究方向?yàn)榫W(wǎng)絡(luò)管理;方奇（1999—?），男，安徽蚌埠人，本科，主要研究方向?yàn)樾畔踩?陶駿（1978—?），男，安徽蕪湖人，碩士，副教授，高級(jí)工程師，主要研究方向?yàn)榫W(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全;馬利祥（1985—?），山東菏澤人，博士，高級(jí)工程師，主要研究方向?yàn)殡娮有畔⒓夹g(shù)。