插入和歸并算法在現(xiàn)代藏文字符排序里的比較

次仁羅增　邊巴旺堆

摘要：選擇一個最優(yōu)的排序算法很重要，因為它能夠幫你可以節(jié)省大量的資源。因此，學習研究排序算法具有重要的理論意義和廣泛的應用價值。首先對排序、插入排序、歸并排序、現(xiàn)代藏文字符排序進行理論分析。然后在Python環(huán)境下實現(xiàn)插入、歸并兩種排序算法的現(xiàn)代藏文字符排序。最后從時間復雜度和空間復雜度來分析比較兩種算法在現(xiàn)代藏文字符排序上的運用。

關(guān)鍵詞：插入排序；歸并排序；算法；現(xiàn)代藏文字符

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2018）19-0181-05

Abstract：It is important to choose an optimal sorting algorithm，Because it can help you save a lot of resources.Therefore， studying the learning ranking algorithm have important theoretical significance and wide application value.This paper analyzes the sorting， inserting sorting， merging sorting and modern Tibetan character sorting.Then in the Python environment，Modern Tibetan characters sorting by inserting and merging two sorting algorithms.Finally， the use of the two algorithms in the sorting of modern Tibetan characters is analyzed and compared from the time complexity and space complexity.

Key words： Insert sorting； merge sort； algorithm； modern Tibetan characters

1 引言

排序算法的選擇和性能分析是一個實際而復雜的問題，在所有的排序算法當中，沒有哪一種算法是最優(yōu)。有些算法適合運用于硬件空間大的情況下，有些適合運用在硬件空間較小的情況下，因此，在實際應用當中，根據(jù)不同的條件選擇，也可以將多種排序方法結(jié)合運用[1]。

實現(xiàn)藏文字符排序算法一般包括兩個步驟：第一要完成藏文字符的構(gòu)建元素識別，第二利用構(gòu)件識別元素的優(yōu)先級來排序，該方法在文獻[2]中已實現(xiàn)。但是該文獻中更多的提到藏文語法規(guī)則，對算法的研究內(nèi)容較少。文獻[3]中研究了藏文詞語的構(gòu)件，建立規(guī)則函數(shù)和構(gòu)建內(nèi)部元素的優(yōu)先級，實現(xiàn)藏文詞典排序方法研究，并設計了識別現(xiàn)代藏文音節(jié)、現(xiàn)代藏文音節(jié)的優(yōu)先級順序兩種算法。但是該文獻中沒有提到具體的運用在哪些排序算法上。

本文學習研究現(xiàn)代藏文字符排序。在學習研究原有的藏文字符排序基礎上實現(xiàn)了插入、歸并兩種的排序算法在現(xiàn)代藏文字符排序上的運用，并從時間復雜度和空間復雜度來分析現(xiàn)代藏文字符運用哪個排序算法更理想。

2 相關(guān)的概念

2.1 排序

排序是計算機編程中一項常見的操作，其中排序算法是如何按照什么方法的要求進行排列記錄。評判一個排序算法主要有兩條標準，一是算法運行所需要的時間；二是算法運行所需要的附加空間。還有算法自身的復雜程度也是需要考慮的。排序本身所需要的空間不大，而算法常常執(zhí)行的是一種運算。屬于系統(tǒng)的核心部分，因此，一個排序算法的時間開銷是衡量它是不是一個好的排序算法的重要標志。時間開銷是通常計算算法執(zhí)行中的數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)來衡量。

（1） 數(shù)據(jù)比較次數(shù)[i=2ni=（n+2）（n-1）/2=O（n2）]

（2） 數(shù)據(jù)移動次數(shù)

[i=2n（i-1+2）=（n-1）（n+4）/2=O（n2）]

2.2 插入排序

插入排序是對一組數(shù)據(jù)依據(jù)某個關(guān)鍵字的大小排列順序把數(shù)據(jù)插入到適當?shù)奈恢蒙?，直到所有?shù)據(jù)插入完成。插入排序類似于我們打撲克的時候：

每次從桌上拿走一張牌并將它插入到左手上；

保持手上牌的順序是正確的；

每次拿上一張新牌按順序插入到手上的排中間。

對于數(shù)組來說，我們就是從第二個元素開始，在該元素左邊建立一個排好序的子數(shù)組，然后對右邊的元素進行依次遍歷，將它們插入到左邊的子數(shù)組中，這樣就排好序。算法分析：時間復雜度：若排序在最好的情況下排序好的，不會進行內(nèi)循環(huán)，所以復雜度為：[O（n）]。在最壞的情況下：[O（n2）]

空間復雜度：[O（1）]

2.3 歸并排序

歸并排序它是在歸并操作上面建立的一種排序算法，算法采用了遞歸分治法進行分組排序。一分為二、二分為四，當每個組的元素只剩一個時有序，然后兩兩合并，最后合并成一個有序表。算法分析：

時間復雜度：在一般情況和最壞的情況下都是：[O（nlogn）]

空間復雜度：存儲數(shù)組：[O（n）]

2.4 現(xiàn)代藏文字符排序

3 算法

3.1 藏文字符集的生成

本文依據(jù)藏字的結(jié)構(gòu)：首先生成基字、上加字+基字、基字+下加字、上加字+基字+下加字、前加字+基字、前加字+基字+下加字、前加字+上加字+基字、前加字+上加字+基字+下加字一共206個藏字作為基礎字，并相應的把這些藏字存放到命名好的集合中以及寫進程序當中，每次都在這些基礎字的基礎上添加元音、后加字、再后加字、帶下加字（）的15個字并相應的寫進文本中。按照軟件的功能命名數(shù)組：

3.2 兩種排序算法

3.2.1 問題描述

藏文不僅有橫向拼寫性，同時也有縱向拼寫性，把每一橫向基本單位又稱為字丁?，F(xiàn)代藏字中，藏文的整基字丁是由1～4 個字符疊加而成的，最多不超過四層。把縱向疊加的部分看作為一個整體后，可以看做是前加字、整個基字丁、后加字、再后加字的線性排列，這跟其它的文字處理方式相同，可以減少藏文的處理難度。這種處理方式雖然減少了處理的難度，但把藏文縱向疊加的屬性完全掩蓋了，不利于藏文信息處理。如果能把藏字的所有構(gòu)件識別后再進行排序，那么對藏字的處理就比較方便了。

3.2.2 問題分析

（1） 理論依據(jù)

藏字靜態(tài)的結(jié)構(gòu)方式由七個構(gòu)件組成，前加字、上加字、基字、下加字、元音、后加字和再后加字構(gòu)成。從上到下第一層到七層，第一層基字層是最核心的層次，是構(gòu)成藏字必不可缺的構(gòu)件。從第二層到第七層分別為上加字、前加字、下加字、元音、后加字、再后加字。第二層到第七層的字符不是構(gòu)成藏字必不可缺的構(gòu)件，是按照藏字的不同以及搭配規(guī)則，每一個字符當中這些構(gòu)件成分是可以缺少的。通過分析《藏漢大詞典》等詞典的排序情況后得到藏字的字典序列是分層循環(huán)其層次如圖2所示。進行對比然后依次先后排序。

4 結(jié)論

在排序算法當中不同的排序方法各自適應的應用環(huán)境和要求不同。本文運用插入、歸并兩種排序算法來實現(xiàn)現(xiàn)代藏文字符排序并比較兩種排序算法。結(jié)果計算插入排序在時間復雜度上界值18784*（（1+18784）/2）*8*8次，在空間復雜度上共需要37570*8個字節(jié)空間。歸并排序在時間復雜度上界值比較次數(shù)16*2^16次，在空間復雜度上共需要131068*8個字節(jié)空間。因此，插入排序在時間復雜度上的運算次數(shù)遠遠多于歸并排序；在存貯空間上歸并排序所占的字節(jié)空間比插入排序多。所以，運行計算機硬件存儲空間比較大的情況下現(xiàn)代藏文字符排序更適合運用歸并排序算法，運行計算機硬件存儲空間小的情況下適合運用插入排序算法。排序算法的種類多，要是現(xiàn)代藏文字符能夠運用更多的排序算法，我們可以依據(jù)自身的不同條件情況來選擇更優(yōu)的排序算法。

參考文獻：

[1] 張靜.常用排序算法的分析與比較[J].河西學院學報，2010，26（02）：69-71.

[2] 邊巴旺堆，卓嘎，陳延利，武強.藏文構(gòu)件元素識別算法研究[J].中文信息學報，2014，28（03）：104-111.

[3] 邊巴旺堆，卓嘎，董志誠，武強，王龍業(yè).藏文排序優(yōu)先級算法研究[J].中文信息學報，2015，29（01）：191-196.

[4] 邊巴旺堆.基于ISO/IEC10646藏文編碼字符集標準的藏文排序算法設計與實現(xiàn)[D].西藏大學，2009.

[5] 高定國，珠杰.藏文信息處理的原理與應用[M].成都：西南交通大學出版社，2014.

[6] 科爾曼等著，段建平等譯.算法導論[M].北京.機械工業(yè)出版社，2013.

[7] 張勤.高中數(shù)學教學中排序算法的分析與討論[J].高等函授學報（自然科學版），2012，25（02）：85-87.

[8] 羅良夫，張麗.LSort字符排序算法研究[J].軟件導刊，2016，15（09）：55-56.

[9] 鄭明秀.常用排序算法時間開銷的實驗統(tǒng)計分析[J].西南民族大學學報（自然科學版），2015，41（06）：723-726.

[10] 高定國，龔育昌.現(xiàn)代藏字全集的屬性統(tǒng)計研究[J].中文信息學報，2005（01）：71-75.

[11] 普頓，群諾，尼瑪扎西.漢文和藏文在信息處理中的比較研究[J].西藏科技，2013（10）：77-80.

[12] 徐壽芳.一種新的高效基數(shù)排序算法[J].湖州職業(yè)技術(shù)學院學報，2008（01）：17-19.

[13] 李梅云.一些常見數(shù)據(jù)排序算法的比較和研究[J].漳州職業(yè)技術(shù)學院學報，2009，11（03）：60-62.