LSort字符排序算法研究

罗良夫张丽

摘要：排序是程序设计过程中的常见问题，在工作生活各个领域有重要意义。介绍多种排序算法的特点，分析经典冒泡排序算法的原理，并从排序效率的角度提出LSort字符算法，该算法通过建立一个有序序列并进行排序，有效提高排序操作效率。

关键词：排序；算法；有序序列

DOIDOI：10.11907/rjdk.161482

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2016）009005502

基金项目基金项目：

作者简介作者简介：罗良夫（1985-），男，湖北武汉人，硕士，武汉工程大学邮电与信息工程学院讲师，研究方向为计算机应用；张丽（1984-），女，湖北武汉人，硕士，湖北交通职业技术学院助教，研究方向为计算数学。

1排序算法的基本概念

随着计算机技术的发展及互联网的普及，各类数据量迅猛增长，导致日常数据查询效率较低，构造一个合适的排序算法可以极大提高工作效率。

传统的排序功能要求给定一个无序数据序列，经过排序操作后，将序列按从大到小或从小到大的顺序排列成有序序列，即：

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

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

排序算法一般分为稳定类算法与不稳定类算法，稳定类算法指当有两个相等记录的关键字Keyword1与Keyword2时，在原数据序列中Keyword1出现在Keyword2之前，经过排序操作后，关键字Keyword1仍然在关键字Keyword2之前；而不稳定排序类算法会在相等的键值中改变记录的相对顺序，所以在构造排序算法过程中，应该尽量避免不稳定类排序算法。目前，稳定类排序算法有冒泡排序算法、合并排序算法等[2]。

2经典冒泡排序算法

冒泡排序算法属于典型的交换类排序算法，交换类算法的主要思想是将待排序数据的关键字进行两两比较，当两个元素的值大小相反时交换其位置，同理依次对所有数据进行两两比较[3]。

经典冒泡排序算法的核心思想是将被排序的无序数据序列N[1..n]进行垂直排列，每个数据N[i]被看作是重量为N[i].m的气泡。根据轻气泡在上重气泡在下的原则，从下往上扫描整个数据序列N，遇到顺序不符的轻气泡时调换其位置。对所有“气泡”进行扫描，使所有“气泡”都符合轻上重下的原则[4]。

每次排序过程都使有序气泡增加1个，在经过n-1次排序后，数据序列中就有n-1个气泡，而无序数据序列中气泡的重量大于或等于有序数据序列中气泡的重量，所以整个排序过程至多需要进行n-1次排序。若在某一次排序中未发现气泡位置交换，则说明待排序的无序序列中所有气泡都满足轻者在上重者在下的原则。

衡量算法优劣一般采用时间复杂度及空间复杂度方法，冒泡排序算法的时间复杂度为O（n2），空间复杂度为O（1）。

3LSort字符排序算法

一个问题往往可采用多种算法进行解决，而算法的优劣将直接影响最终程序的效率。算法分析的目的在于选择合适算法和改进算法，冒泡排序算法在多种情况下，每个元素都需要与其它n-1个元素进行比较，在对大量数据进行排序操作时效率较低。为了提高排序操作的效率，本文设计一种新的排序方法—LSort字符排序算法。

其核心思想是对于一个无序字符序列，另外开辟一个与原来序列相同大小的空序列，新序列中要求所有存储元素都是有序的，即添加的元素与新序列中的每个元素进行比较，比如元素3添加到新序列：1，2，4，5中时，将元素3与第1个元素比较，当比较到元素4时，将元素4和5往后退一个空间，然后将3放到元素4之前的位置，具体实现代码如下：

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]；//构造新的元素序列

memset（str，0，n+2）；

*str=*s；

len++；

for（i=1；i

b=true；

for（j=0；j<=len；j++）{//将原序列的元素与新序列进行比较

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字符排序算法的时间复杂度

算法的时间复杂度在计算机科学中是一个函数，大概描述了算法的运行时间。时间复杂度一般使用“O”符号表达，结果一般以最高阶次为准，不考虑函数的低阶项和各项系数。时间复杂度一般考察输入值趋近无穷时的情况[5]。

排序算法中的基本操作重复执行的问题是规模n的函数，假设问题的规模是n，基本操作重复执行的次数是函数 f（n），那么时间复杂度记作：T（n）=O（f（n））。

排序算法花费的时间与算法中语句的执行次数成正比，语句执行次数越多，对应的时间复杂度就越大。算法的时间频度从理论上不能直接计算出来，需要上机试运行才能得到具体频度值。时间复杂度一般考虑问题规模 n 的增长率，一般考虑重复执行次数关于n的阶数。

LSort算法中for循环操作重复n-1次，其它赋值判断等操作重复n-1次，所以LSort算法的时间复杂度T（n）=O（n）。

5LSort字符排序算法的空间复杂度

空间复杂度是对算法运行过程中占用存储空间的一种量度。通过算法空间复杂度计算，可对程序运行所需内存的多少进行预估。算法执行除了包含程序本身所使用的指令、常数、变量和输入数据外，还需包含对数据进行操作的工作单元，以及部分辅助存储空间[5]。程序运行过程执行的存储空间主要分为以下两部分：

（1）固定空间：固定空间部分的大小与输入/出数据个数无关。主要包含代码空间、数据空间，属于静态存储空间。

（2）可调空间：主要包括动态分配的空间，以及递归堆栈所用的空间等，与算法有关。

算法空间复杂度一般考虑程序在运行过程中为局部变量分配的存储空间，具体包括形参列表分配的存储空间大小，以及在函数体中定义的局部变量的存储空间。对于递归类算法，空间复杂度等于所用堆栈空间的大小，等于调用所用的临时存储空间乘以被调用次数的积。

算法空间复杂度一般以数量级的形式表示，例如一个算法的空间复杂度为常量，即不随规模n的大小而改变时，算法空间复杂度等于O（1）；当算法的空间复杂度与规模n呈线性比例关系时，可表示为O（n）；当算法的空间复杂度与log2n成正比时，可表示为O（log2n）。假设形参为数组类型，只需为它分配实参传送来的地址指针所占用的空间；假如形参为引用类型，只需要分配存储地址所占用的存储空间。

LSort算法排序过程中，新序列所使用的空间为常量，且规模n的增长对空间并没有产生影响，所以其空间复杂度S（n）=O（1）。

6结语

本文分析了排序算法的特点，讨论了经典冒泡排序算法的核心思想，并针对冒泡排序算法的效率提出了LSort字符排序算法。通过建立新的有序列表，能有效减少排序过程中的比较次数，经测试该算法适合对大量无序字符数据进行排序。

参考文献参考文献：

[1]王红梅. 数据结构（C++版）[M].北京：清华大学出版社，2011：167188.

[2]贾丹. 排序算法的性能分析[J]. 电脑知识与技术，2015（26）：75.

[3]钟全. 简单选择排序算法稳定性探究及其改进[J]. 软件导刊，2016（2）：6063.

[4]张朝鑫. C语言中的冒泡排序算法优化究[J]. 硅谷，2013（19）：166.

[5]殷超. 常用算法时间复杂度的计算方法[J]. 科技信息，2011（29）：87.

责任编辑（责任编辑：陈福时）