插入和归并算法在现代藏文字符排序里的比较

次仁罗增　边巴旺堆

摘要：选择一个最优的排序算法很重要，因为它能够帮你可以节省大量的资源。因此，学习研究排序算法具有重要的理论意义和广泛的应用价值。首先对排序、插入排序、归并排序、现代藏文字符排序进行理论分析。然后在Python环境下实现插入、归并两种排序算法的现代藏文字符排序。最后从时间复杂度和空间复杂度来分析比较两种算法在现代藏文字符排序上的运用。

关键词：插入排序；归并排序；算法；现代藏文字符

中图分类号：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 引言

排序算法的选择和性能分析是一个实际而复杂的问题，在所有的排序算法当中，没有哪一种算法是最优。有些算法适合运用于硬件空间大的情况下，有些适合运用在硬件空间较小的情况下，因此，在实际应用当中，根据不同的条件选择，也可以将多种排序方法结合运用[1]。

实现藏文字符排序算法一般包括两个步骤：第一要完成藏文字符的构建元素识别，第二利用构件识别元素的优先级来排序，该方法在文献[2]中已实现。但是该文献中更多的提到藏文语法规则，对算法的研究内容较少。文献[3]中研究了藏文词语的构件，建立规则函数和构建内部元素的优先级，实现藏文词典排序方法研究，并设计了识别现代藏文音节、现代藏文音节的优先级顺序两种算法。但是该文献中没有提到具体的运用在哪些排序算法上。

本文学习研究现代藏文字符排序。在学习研究原有的藏文字符排序基础上实现了插入、归并两种的排序算法在现代藏文字符排序上的运用，并从时间复杂度和空间复杂度来分析现代藏文字符运用哪个排序算法更理想。

2 相关的概念

2.1 排序

排序是计算机编程中一项常见的操作，其中排序算法是如何按照什么方法的要求进行排列记录。评判一个排序算法主要有两条标准，一是算法运行所需要的时间；二是算法运行所需要的附加空间。还有算法自身的复杂程度也是需要考虑的。排序本身所需要的空间不大，而算法常常执行的是一种运算。属于系统的核心部分，因此，一个排序算法的时间开销是衡量它是不是一个好的排序算法的重要标志。时间开销是通常计算算法执行中的数据比较次数和数据移动次数来衡量。

（1） 数据比较次数[i=2ni=（n+2）（n-1）/2=O（n2）]

（2） 数据移动次数

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

2.2 插入排序

插入排序是对一组数据依据某个关键字的大小排列顺序把数据插入到适当的位置上，直到所有数据插入完成。插入排序类似于我们打扑克的时候：

每次从桌上拿走一张牌并将它插入到左手上；

保持手上牌的顺序是正确的；

每次拿上一张新牌按顺序插入到手上的排中间。

对于数组来说，我们就是从第二个元素开始，在该元素左边建立一个排好序的子数组，然后对右边的元素进行依次遍历，将它们插入到左边的子数组中，这样就排好序。算法分析：时间复杂度：若排序在最好的情况下排序好的，不会进行内循环，所以复杂度为：[O（n）]。在最坏的情况下：[O（n2）]

空间复杂度：[O（1）]

2.3 归并排序

归并排序它是在归并操作上面建立的一种排序算法，算法采用了递归分治法进行分组排序。一分为二、二分为四，当每个组的元素只剩一个时有序，然后两两合并，最后合并成一个有序表。算法分析：

时间复杂度：在一般情况和最坏的情况下都是：[O（nlogn）]

空间复杂度：存储数组：[O（n）]

2.4 现代藏文字符排序

3 算法

3.1 藏文字符集的生成

本文依據藏字的结构：首先生成基字、上加字+基字、基字+下加字、上加字+基字+下加字、前加字+基字、前加字+基字+下加字、前加字+上加字+基字、前加字+上加字+基字+下加字一共206个藏字作为基础字，并相应的把这些藏字存放到命名好的集合中以及写进程序当中，每次都在这些基础字的基础上添加元音、后加字、再后加字、带下加字（）的15个字并相应的写进文本中。按照软件的功能命名数组：

3.2 两种排序算法

3.2.1 问题描述

藏文不仅有横向拼写性，同时也有纵向拼写性，把每一横向基本单位又称为字丁。现代藏字中，藏文的整基字丁是由1～4 个字符叠加而成的，最多不超过四层。把纵向叠加的部分看作为一个整体后，可以看做是前加字、整个基字丁、后加字、再后加字的线性排列，这跟其它的文字处理方式相同，可以减少藏文的处理难度。这种处理方式虽然减少了处理的难度，但把藏文纵向叠加的属性完全掩盖了，不利于藏文信息处理。如果能把藏字的所有构件识别后再进行排序，那么对藏字的处理就比较方便了。

3.2.2 问题分析

（1） 理论依据

藏字静态的结构方式由七个构件组成，前加字、上加字、基字、下加字、元音、后加字和再后加字构成。从上到下第一层到七层，第一层基字层是最核心的层次，是构成藏字必不可缺的构件。从第二层到第七层分别为上加字、前加字、下加字、元音、后加字、再后加字。第二层到第七层的字符不是构成藏字必不可缺的构件，是按照藏字的不同以及搭配規则，每一个字符当中这些构件成分是可以缺少的。通过分析《藏汉大词典》等词典的排序情况后得到藏字的字典序列是分层循环其层次如图2所示。进行对比然后依次先后排序。

4 结论

在排序算法当中不同的排序方法各自适应的应用环境和要求不同。本文运用插入、归并两种排序算法来实现现代藏文字符排序并比较两种排序算法。结果计算插入排序在时间复杂度上界值18784*（（1+18784）/2）*8*8次，在空间复杂度上共需要37570*8个字节空间。归并排序在时间复杂度上界值比较次数16*2^16次，在空间复杂度上共需要131068*8个字节空间。因此，插入排序在时间复杂度上的运算次数远远多于归并排序；在存贮空间上归并排序所占的字节空间比插入排序多。所以，运行计算机硬件存储空间比较大的情况下现代藏文字符排序更适合运用归并排序算法，运行计算机硬件存储空间小的情况下适合运用插入排序算法。排序算法的种类多，要是现代藏文字符能够运用更多的排序算法，我们可以依据自身的不同条件情况来选择更优的排序算法。

参考文献：

[1] 张静.常用排序算法的分析与比较[J].河西学院学报，2010，26（02）：69-71.

[2] 边巴旺堆，卓嘎，陈延利，武强.藏文构件元素识别算法研究[J].中文信息学报，2014，28（03）：104-111.

[3] 边巴旺堆，卓嘎，董志诚，武强，王龙业.藏文排序优先级算法研究[J].中文信息学报，2015，29（01）：191-196.

[4] 边巴旺堆.基于ISO/IEC10646藏文编码字符集标准的藏文排序算法设计与实现[D].西藏大学，2009.

[5] 高定国，珠杰.藏文信息处理的原理与应用[M].成都：西南交通大学出版社，2014.

[6] 科尔曼等著，段建平等译.算法导论[M].北京.机械工业出版社，2013.

[7] 张勤.高中数学教学中排序算法的分析与讨论[J].高等函授学报（自然科学版），2012，25（02）：85-87.

[8] 罗良夫，张丽.LSort字符排序算法研究[J].软件导刊，2016，15（09）：55-56.

[9] 郑明秀.常用排序算法时间开销的实验统计分析[J].西南民族大学学报（自然科学版），2015，41（06）：723-726.

[10] 高定国，龚育昌.现代藏字全集的属性统计研究[J].中文信息学报，2005（01）：71-75.

[11] 普顿，群诺，尼玛扎西.汉文和藏文在信息处理中的比较研究[J].西藏科技，2013（10）：77-80.

[12] 徐寿芳.一种新的高效基数排序算法[J].湖州职业技术学院学报，2008（01）：17-19.

[13] 李梅云.一些常见数据排序算法的比较和研究[J].漳州职业技术学院学报，2009，11（03）：60-62.