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

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

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

中圖分類號：TP312?文獻標識碼：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)秀的排序算法，它的平均時間復(fù)雜度為O（n*log2n），與冒泡排序和插入排序相比較而言，已經(jīng)有了很大的提高，n指待排序數(shù)據(jù)的規(guī)模，n越大，快速排序的優(yōu)勢越明顯[1]。

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

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

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

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

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

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

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

2 改進的快速排序算法

傳統(tǒng)快速排序算法在序列基本有序的情況下效率較差，這是由于關(guān)鍵值選擇不合理而導(dǎo)致的，因為首元素并不能把一個序列劃分成兩個大致相等的子序列，而采取序列平均值作為關(guān)鍵值進行劃分，效果會優(yōu)越得多[5]。

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

4 結(jié)論

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

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

作者簡介：應(yīng)沈靜（2000—?），女，浙江麗水人，本科，主要研究方向為網(wǎng)絡(luò)管理;方奇（1999—?），男，安徽蚌埠人，本科，主要研究方向為信息安全;陶駿（1978—?），男，安徽蕪湖人，碩士，副教授，高級工程師，主要研究方向為網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全;馬利祥（1985—?），山東菏澤人，博士，高級工程師，主要研究方向為電子信息技術(shù)。