一種新的排序算法研究

王偉全，陸攀，曹均闊，張學(xué)平

一種新的排序算法研究

王偉全，陸攀，曹均闊，張學(xué)平

排序是計(jì)算機(jī)科學(xué)中最重要的研究問(wèn)題之一。介紹了一種新的排序算法，全面深入地分析了擠壓式排序的算法思想以及算法實(shí)現(xiàn)，并對(duì)該算法在時(shí)間和空間上的復(fù)雜度進(jìn)行了分析，與快速排序算法、希爾排序算法進(jìn)行了理論上的對(duì)比。理論分析及實(shí)驗(yàn)數(shù)據(jù)表明，該算法是正確的，可行的，在同類排序算法中有明顯優(yōu)勢(shì)。

擠壓式排序；遞歸；歸并；算法

0 引言

排序（Sorting），就是將數(shù)據(jù)元素（或記錄）的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。由于排序是計(jì)算機(jī)科學(xué)中一項(xiàng)復(fù)雜而重要的技術(shù)，無(wú)論在系統(tǒng)軟件還是在應(yīng)用軟件中使用頻率都很高[2]，排序算法在最短路徑算法中的應(yīng)用起著關(guān)鍵性的作用，在通信、衛(wèi)星拓?fù)渚W(wǎng)絡(luò)、地理信息系統(tǒng)（GIS）和計(jì)算機(jī)網(wǎng)絡(luò)等的研究和應(yīng)用中起著基礎(chǔ)性的作用[3]。由此可見，排序算法在實(shí)際的軟件中發(fā)揮著重要的作用。

目前已有的排序算法都難以在任何情況下都保持較快的速度，所以對(duì)新的排序算法的研究是有實(shí)際價(jià)值的。性能較優(yōu)的算法有快速排序、歸并排序等，其中快速排序主要運(yùn)用了遞歸的思想，歸并排序則運(yùn)用了歸并的方法。結(jié)合快速排序的遞歸算法和歸并排序的歸并思想，本文提出一種新的算法-擠壓排序。該算法時(shí)間和空間性能較好，在海量數(shù)據(jù)排序中優(yōu)勢(shì)較突出。

1 算法描述與實(shí)現(xiàn)

1.1 算法思想

擠壓排序，顧名思義就是整個(gè)排序過(guò)程采用類似“擠壓”的方式來(lái)實(shí)現(xiàn)。該算法融合了遞歸與歸并的思想，具體思想闡述如下：

定義2個(gè)數(shù)組：Data[1...n]存儲(chǔ)待排序的元素，Sorted[1...n]存儲(chǔ)已排好序的元素。以下分別簡(jiǎn)稱為D和S。

第一步：通過(guò)第一趟排序?qū)⒋判驍?shù)組D分成三個(gè)部分，其中兩個(gè)部分分別存放在數(shù)組S的前部和后部，前部元素的值要比后面所有元素的值小，第三個(gè)部分覆蓋到數(shù)組D的前部。

第二步：對(duì)數(shù)組S的前部和后部進(jìn)行歸并，將歸并結(jié)果存放在數(shù)組S的前部。

第三步：按照此方法對(duì)剛剛放在數(shù)組D中的第三個(gè)部分進(jìn)行擠壓排序，直到數(shù)組S中的元素是數(shù)組D中的所有元素的有序排列。

1.2 算法推演

為了更直觀地描述和分析算法，現(xiàn)以實(shí)際數(shù)據(jù)為例進(jìn)行算法推演。數(shù)組定義見2.1所述，

max、min、unsorted_so_far、sorted_so_far分別記錄最大值、最小值、未排序的個(gè)數(shù)和已排序的個(gè)數(shù)，假定初始數(shù)組D為{34,53,21,78,123,25,110,28,84}，數(shù)組S為空。

排序過(guò)程:

（1）將數(shù)組D分割成3個(gè)部分，其中兩個(gè)部分分別存儲(chǔ)在數(shù)組S的前部和后部。結(jié)果狀態(tài)為：D{25，110，28，84，123，25，110，28，84}，S{21，null,null,null,null，123，78，53，34}。（分割原則：初始化max=min=D[0],當(dāng)D[i]＞=max,將該元素在數(shù)組S中從下標(biāo)為n-1向前放,并更新max的值;當(dāng)D[i]＜min時(shí)，將該元素在數(shù)組S中從sorted_so_far位置往后放,并更新min的值。當(dāng)不滿足前兩個(gè)條件時(shí)，把該元素在數(shù)組D中從下標(biāo)為0開始存放。）從分割結(jié)束的數(shù)組D可知，前4個(gè)元素沒有轉(zhuǎn)移到數(shù)組S中，意味著本趟排序操作對(duì)這4個(gè)元素沒有影響，此時(shí)unsorted_so_far=4，等待下一趟排序。

（2）對(duì)數(shù)組S的前部和后部進(jìn)行歸并，以數(shù)組D為中介，暫時(shí)存放歸并結(jié)果。歸并結(jié)束后，將結(jié)果復(fù)制并覆蓋到數(shù)組S的前部。結(jié)果狀態(tài)為：D{25，110，28，84，123，78，53，34，21}，S{123，78，53，34，21，123，78，53，34}。此時(shí)，由數(shù)組S可知，前面5個(gè)元素已有序，剩下4個(gè)元素待排序。

（3）當(dāng)上述（2）執(zhí)行完畢后，第一趟排序結(jié)束。然后把步驟（1）所得結(jié)果數(shù)組D中前4個(gè)元素（斜體）依次用上述步驟完成整個(gè)擠壓排序過(guò)程，最后直到unsorted_so_far=0,數(shù)組S中的元素即全部有序（S{123，110，84，78，53，34，28，25，21}），排序完成。

2.3 算法實(shí)現(xiàn)（C++）

//定義全局變量，分別用于記錄待排序的個(gè)數(shù)，已排好序的個(gè)數(shù)，未排序的個(gè)數(shù)

2 算法復(fù)雜度分析

2.1 空間復(fù)雜度

實(shí)現(xiàn)該算法過(guò)程中，除數(shù)組D外，另外需申請(qǐng)一個(gè)數(shù)組S，實(shí)現(xiàn)該算法需2n的空間,故空間復(fù)雜度為O(n)。

2.2 時(shí)間復(fù)雜度

該算法的時(shí)間復(fù)雜度主要取決于遞歸的次數(shù)，當(dāng)不考慮排序時(shí)遞歸的次數(shù)，算法的時(shí)間復(fù)雜度為O(n)。令遞歸次數(shù)為c次，那么c的值可能會(huì)根據(jù)排序序列的不同而不同。最好情況下為c=0時(shí)（即經(jīng)過(guò)0次遞歸就已經(jīng)排序完成），例如序列68,72,43,81,88,30,108,12,5,129……，按照此規(guī)律排列的數(shù)可以不用經(jīng)過(guò)遞歸就可實(shí)現(xiàn)排序（規(guī)律：從第一個(gè)元素開始一部分元素（斜體）一直遞增，另一部分元素一直遞減）滿足上述規(guī)律的數(shù)據(jù)序列，該算法可以高效地對(duì)序列進(jìn)行排序，時(shí)間復(fù)雜度為O(n)。最壞情況是每次遞歸只能擠壓兩個(gè)數(shù)，例如序列1，100，2，99，3，98，4，96，5，95……，這種情況下該算法是比較低效率的，時(shí)間復(fù)雜度為2+4+6+……+(n-2)+n=O(n^2)。

2.3 復(fù)雜度對(duì)比分析

（1）快速排序

快速排序算法的基本思想：在數(shù)組中選擇一個(gè)軸值，將其它數(shù)與軸值比較，比軸值小的數(shù)放在軸值左邊，比軸值大的數(shù)放在右邊。于是，數(shù)組就分割成了兩個(gè)子數(shù)組，遞歸執(zhí)行上述步驟，直到子數(shù)組變成兩個(gè)元素為止。

時(shí)間復(fù)雜度：最好情況下為O(nlogn)，最壞情況下為O(n^2)。

空間復(fù)雜度：需O(logn)的輔助空間。

（2）冒泡排序

冒泡排序算法的基本思想：將被排序的數(shù)組D[1...n]垂直排列，每個(gè)元素D[i]視為重量為D[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組D，凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。

時(shí)間復(fù)雜度：最好情況下（初始為正序），只需通過(guò)n-1次比較，不需要移動(dòng)關(guān)鍵字，即為O(n)；最壞情況下（初始為逆序），須進(jìn)行n(n-1)/2次比較，即為O(n^2)[4]。

空間復(fù)雜度：整個(gè)排序過(guò)程為比較交換，需O(1)的輔助空間。

表1 復(fù)雜度對(duì)比分析情況表

3 算法性能對(duì)比分析

對(duì)大量數(shù)據(jù)進(jìn)行多次測(cè)試（數(shù)據(jù)由隨機(jī)函數(shù)Rand()產(chǎn)生），多次測(cè)試結(jié)果如下表：

表2 大數(shù)據(jù)下算法性能測(cè)試對(duì)比分析情況表

由上表對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)分析可得：擠壓排序在時(shí)間性能上略低于快速排序，但卻比冒泡排序快很多。

4 總結(jié)

本文研究提出的擠壓排序算法是合理的、有效的，具有一定的先進(jìn)性和應(yīng)用前景。

[1]霍紅衛(wèi),許進(jìn).快速排序算法研究[J].微電子學(xué)與計(jì)算機(jī),2002.

[2]周建欽.超快速排序算法[J].計(jì)算機(jī)工程與應(yīng)用,2006.

[3]汪維清,羅先文,汪維華.分組排序算法[J].計(jì)算機(jī)工程與應(yīng)用,2008.

[4]淦艷,楊有.五種排序算法的性能分析[J].重慶文理學(xué)院學(xué)報(bào)(自然科學(xué)版),2010.

[5]Clifford A.Shaffer.Data Structures and Algorithm Analysis in C++[M].北京:電子工業(yè)出版社,2013.

Study on a New Sort Algorithm

Wang Weiquan1,Lu Pan2,Cao Junkuo3,Zhang Xueping3
(1.Network Management Center,Hainan Medical University,Haikou 571199,China; 2.College of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,China; 3.College of Information Science and Technology,Hainan Normal University,Haikou 571100,China)

Sorting is one of the most important research problems in the area of Computer Science.In this paper,a new sorting algorithm called Squeeze sort is introduced.There are detailed analyses about the thought of this sorting algorithm and the comparison with Quick sort and Shell sort in theory in the paper.It also gives the algorithm implementation in C++.Both theoretical analysis and experimental tests confirm that Squeeze sort algorithm is correct，feasible and has obvious advantages when compared with other algorithms using similar methods.

Squeeze Sort;Recursion;Merge;Algorithm

TP311

A

1007-757X(2015)06-0061-02

2014.12.07）

王偉全（1984-），男，海南醫(yī)學(xué)院，實(shí)驗(yàn)師，學(xué)士，研究方向：智能算法、數(shù)據(jù)庫(kù)、網(wǎng)絡(luò)，?？冢?71199

陸 攀（1996-），男，華南理工大學(xué)，大學(xué)本科，研究方向：智能算法、數(shù)據(jù)庫(kù)、手機(jī)應(yīng)用開發(fā)，廣州，510006

曹均闊（1973-），男，海南師范大學(xué)，副教授，博士，研究方向：智能算法、數(shù)據(jù)庫(kù)、嵌入式開發(fā)、手機(jī)應(yīng)用開發(fā)，?？?，571100

張學(xué)平（1963-），男，海南師范大學(xué)，副教授，學(xué)士，研究方向：智能算法、數(shù)據(jù)庫(kù)，海口，571100