一種新的排序算法研究

王偉全，陸攀，曹均闊，張學平

一種新的排序算法研究

王偉全，陸攀，曹均闊，張學平

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

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

0 引言

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

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

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

1.1 算法思想

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

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

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

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

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

1.2 算法推演

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

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

排序過程:

（1）將數(shù)組D分割成3個部分，其中兩個部分分別存儲在數(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[i]＞=max,將該元素在數(shù)組S中從下標為n-1向前放,并更新max的值;當D[i]＜min時，將該元素在數(shù)組S中從sorted_so_far位置往后放,并更新min的值。當不滿足前兩個條件時，把該元素在數(shù)組D中從下標為0開始存放。）從分割結(jié)束的數(shù)組D可知，前4個元素沒有轉(zhuǎn)移到數(shù)組S中，意味著本趟排序操作對這4個元素沒有影響，此時unsorted_so_far=4，等待下一趟排序。

（2）對數(shù)組S的前部和后部進行歸并，以數(shù)組D為中介，暫時存放歸并結(jié)果。歸并結(jié)束后，將結(jié)果復制并覆蓋到數(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ù)組S可知，前面5個元素已有序，剩下4個元素待排序。

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

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

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

2 算法復雜度分析

2.1 空間復雜度

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

2.2 時間復雜度

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

2.3 復雜度對比分析

（1）快速排序

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

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

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

（2）冒泡排序

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

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

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

表1 復雜度對比分析情況表

3 算法性能對比分析

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

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

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

4 總結(jié)

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

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

[2]周建欽.超快速排序算法[J].計算機工程與應用,2006.

[3]汪維清,羅先文,汪維華.分組排序算法[J].計算機工程與應用,2008.

[4]淦艷,楊有.五種排序算法的性能分析[J].重慶文理學院學報(自然科學版),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ī)學院，實驗師，學士，研究方向：智能算法、數(shù)據(jù)庫、網(wǎng)絡，海口，571199

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

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

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