LSort字符排序算法研究

羅良夫張麗

摘要：排序是程序設(shè)計(jì)過程中的常見問題，在工作生活各個(gè)領(lǐng)域有重要意義。介紹多種排序算法的特點(diǎn)，分析經(jīng)典冒泡排序算法的原理，并從排序效率的角度提出LSort字符算法，該算法通過建立一個(gè)有序序列并進(jìn)行排序，有效提高排序操作效率。

關(guān)鍵詞：排序；算法；有序序列

DOIDOI：10.11907/rjdk.161482

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2016）009005502

基金項(xiàng)目基金項(xiàng)目：

作者簡介作者簡介：羅良夫（1985-），男，湖北武漢人，碩士，武漢工程大學(xué)郵電與信息工程學(xué)院講師，研究方向?yàn)橛?jì)算機(jī)應(yīng)用；張麗（1984-），女，湖北武漢人，碩士，湖北交通職業(yè)技術(shù)學(xué)院助教，研究方向?yàn)橛?jì)算數(shù)學(xué)。

1排序算法的基本概念

隨著計(jì)算機(jī)技術(shù)的發(fā)展及互聯(lián)網(wǎng)的普及，各類數(shù)據(jù)量迅猛增長，導(dǎo)致日常數(shù)據(jù)查詢效率較低，構(gòu)造一個(gè)合適的排序算法可以極大提高工作效率。

傳統(tǒng)的排序功能要求給定一個(gè)無序數(shù)據(jù)序列，經(jīng)過排序操作后，將序列按從大到小或從小到大的順序排列成有序序列，即：

輸入序列：N1，N2，N3，...，Nn

輸出序列：N1=N2>=N3>=...>=Nn[1]。

排序算法一般分為穩(wěn)定類算法與不穩(wěn)定類算法，穩(wěn)定類算法指當(dāng)有兩個(gè)相等記錄的關(guān)鍵字Keyword1與Keyword2時(shí)，在原數(shù)據(jù)序列中Keyword1出現(xiàn)在Keyword2之前，經(jīng)過排序操作后，關(guān)鍵字Keyword1仍然在關(guān)鍵字Keyword2之前；而不穩(wěn)定排序類算法會(huì)在相等的鍵值中改變記錄的相對(duì)順序，所以在構(gòu)造排序算法過程中，應(yīng)該盡量避免不穩(wěn)定類排序算法。目前，穩(wěn)定類排序算法有冒泡排序算法、合并排序算法等[2]。

2經(jīng)典冒泡排序算法

冒泡排序算法屬于典型的交換類排序算法，交換類算法的主要思想是將待排序數(shù)據(jù)的關(guān)鍵字進(jìn)行兩兩比較，當(dāng)兩個(gè)元素的值大小相反時(shí)交換其位置，同理依次對(duì)所有數(shù)據(jù)進(jìn)行兩兩比較[3]。

經(jīng)典冒泡排序算法的核心思想是將被排序的無序數(shù)據(jù)序列N[1..n]進(jìn)行垂直排列，每個(gè)數(shù)據(jù)N[i]被看作是重量為N[i].m的氣泡。根據(jù)輕氣泡在上重氣泡在下的原則，從下往上掃描整個(gè)數(shù)據(jù)序列N，遇到順序不符的輕氣泡時(shí)調(diào)換其位置。對(duì)所有“氣泡”進(jìn)行掃描，使所有“氣泡”都符合輕上重下的原則[4]。

每次排序過程都使有序氣泡增加1個(gè)，在經(jīng)過n-1次排序后，數(shù)據(jù)序列中就有n-1個(gè)氣泡，而無序數(shù)據(jù)序列中氣泡的重量大于或等于有序數(shù)據(jù)序列中氣泡的重量，所以整個(gè)排序過程至多需要進(jìn)行n-1次排序。若在某一次排序中未發(fā)現(xiàn)氣泡位置交換，則說明待排序的無序序列中所有氣泡都滿足輕者在上重者在下的原則。

衡量算法優(yōu)劣一般采用時(shí)間復(fù)雜度及空間復(fù)雜度方法，冒泡排序算法的時(shí)間復(fù)雜度為O（n2），空間復(fù)雜度為O（1）。

3LSort字符排序算法

一個(gè)問題往往可采用多種算法進(jìn)行解決，而算法的優(yōu)劣將直接影響最終程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法，冒泡排序算法在多種情況下，每個(gè)元素都需要與其它n-1個(gè)元素進(jìn)行比較，在對(duì)大量數(shù)據(jù)進(jìn)行排序操作時(shí)效率較低。為了提高排序操作的效率，本文設(shè)計(jì)一種新的排序方法—LSort字符排序算法。

其核心思想是對(duì)于一個(gè)無序字符序列，另外開辟一個(gè)與原來序列相同大小的空序列，新序列中要求所有存儲(chǔ)元素都是有序的，即添加的元素與新序列中的每個(gè)元素進(jìn)行比較，比如元素3添加到新序列：1，2，4，5中時(shí)，將元素3與第1個(gè)元素比較，當(dāng)比較到元素4時(shí)，將元素4和5往后退一個(gè)空間，然后將3放到元素4之前的位置，具體實(shí)現(xiàn)代碼如下：

char* LString：：LShengxu（char *s）{

char *str；

int n=0 ， i ， j ， k ， len=0；

bool b；

while（*（s+n）！=0）{

n++；

}

str=new char[n+2]；//構(gòu)造新的元素序列

memset（str，0，n+2）；

*str=*s；

len++；

for（i=1；i

b=true；

for（j=0；j<=len；j++）{//將原序列的元素與新序列進(jìn)行比較

if（*（s+i）<*（str+j））{//確定新添加的元素在新序列中的位置

for（k=len；k>=j；k--）//將新序列中新元素位置后的元素后移一位

*（str+k+1）=*（str+k）；

*（str+j）=*（s+i）；

b=false；

break；

}

}

if（true==b）

*（str+len）=*（s+i）；

len++；

}

*（str+n）=0；

for（i=0；i

*（s+i）=*（str+i）；

delete []str；

return s；

}

4LSort字符排序算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度在計(jì)算機(jī)科學(xué)中是一個(gè)函數(shù)，大概描述了算法的運(yùn)行時(shí)間。時(shí)間復(fù)雜度一般使用“O”符號(hào)表達(dá)，結(jié)果一般以最高階次為準(zhǔn)，不考慮函數(shù)的低階項(xiàng)和各項(xiàng)系數(shù)。時(shí)間復(fù)雜度一般考察輸入值趨近無窮時(shí)的情況[5]。

排序算法中的基本操作重復(fù)執(zhí)行的問題是規(guī)模n的函數(shù)，假設(shè)問題的規(guī)模是n，基本操作重復(fù)執(zhí)行的次數(shù)是函數(shù) f（n），那么時(shí)間復(fù)雜度記作：T（n）=O（f（n））。

排序算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比，語句執(zhí)行次數(shù)越多，對(duì)應(yīng)的時(shí)間復(fù)雜度就越大。算法的時(shí)間頻度從理論上不能直接計(jì)算出來，需要上機(jī)試運(yùn)行才能得到具體頻度值。時(shí)間復(fù)雜度一般考慮問題規(guī)模 n 的增長率，一般考慮重復(fù)執(zhí)行次數(shù)關(guān)于n的階數(shù)。

LSort算法中for循環(huán)操作重復(fù)n-1次，其它賦值判斷等操作重復(fù)n-1次，所以LSort算法的時(shí)間復(fù)雜度T（n）=O（n）。

5LSort字符排序算法的空間復(fù)雜度

空間復(fù)雜度是對(duì)算法運(yùn)行過程中占用存儲(chǔ)空間的一種量度。通過算法空間復(fù)雜度計(jì)算，可對(duì)程序運(yùn)行所需內(nèi)存的多少進(jìn)行預(yù)估。算法執(zhí)行除了包含程序本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需包含對(duì)數(shù)據(jù)進(jìn)行操作的工作單元，以及部分輔助存儲(chǔ)空間[5]。程序運(yùn)行過程執(zhí)行的存儲(chǔ)空間主要分為以下兩部分：

（1）固定空間：固定空間部分的大小與輸入/出數(shù)據(jù)個(gè)數(shù)無關(guān)。主要包含代碼空間、數(shù)據(jù)空間，屬于靜態(tài)存儲(chǔ)空間。

（2）可調(diào)空間：主要包括動(dòng)態(tài)分配的空間，以及遞歸堆棧所用的空間等，與算法有關(guān)。

算法空間復(fù)雜度一般考慮程序在運(yùn)行過程中為局部變量分配的存儲(chǔ)空間，具體包括形參列表分配的存儲(chǔ)空間大小，以及在函數(shù)體中定義的局部變量的存儲(chǔ)空間。對(duì)于遞歸類算法，空間復(fù)雜度等于所用堆?？臻g的大小，等于調(diào)用所用的臨時(shí)存儲(chǔ)空間乘以被調(diào)用次數(shù)的積。

算法空間復(fù)雜度一般以數(shù)量級(jí)的形式表示，例如一個(gè)算法的空間復(fù)雜度為常量，即不隨規(guī)模n的大小而改變時(shí)，算法空間復(fù)雜度等于O（1）；當(dāng)算法的空間復(fù)雜度與規(guī)模n呈線性比例關(guān)系時(shí)，可表示為O（n）；當(dāng)算法的空間復(fù)雜度與log2n成正比時(shí)，可表示為O（log2n）。假設(shè)形參為數(shù)組類型，只需為它分配實(shí)參傳送來的地址指針?biāo)加玫目臻g；假如形參為引用類型，只需要分配存儲(chǔ)地址所占用的存儲(chǔ)空間。

LSort算法排序過程中，新序列所使用的空間為常量，且規(guī)模n的增長對(duì)空間并沒有產(chǎn)生影響，所以其空間復(fù)雜度S（n）=O（1）。

6結(jié)語

本文分析了排序算法的特點(diǎn)，討論了經(jīng)典冒泡排序算法的核心思想，并針對(duì)冒泡排序算法的效率提出了LSort字符排序算法。通過建立新的有序列表，能有效減少排序過程中的比較次數(shù)，經(jīng)測試該算法適合對(duì)大量無序字符數(shù)據(jù)進(jìn)行排序。

參考文獻(xiàn)參考文獻(xiàn)：

[1]王紅梅. 數(shù)據(jù)結(jié)構(gòu)（C++版）[M].北京：清華大學(xué)出版社，2011：167188.

[2]賈丹. 排序算法的性能分析[J]. 電腦知識(shí)與技術(shù)，2015（26）：75.

[3]鐘全. 簡單選擇排序算法穩(wěn)定性探究及其改進(jìn)[J]. 軟件導(dǎo)刊，2016（2）：6063.

[4]張朝鑫. C語言中的冒泡排序算法優(yōu)化究[J]. 硅谷，2013（19）：166.

[5]殷超. 常用算法時(shí)間復(fù)雜度的計(jì)算方法[J]. 科技信息，2011（29）：87.

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）