LSort字符排序算法研究.docVIP

LSort字符排序算法研究 　　摘要：排序是程序设计过程中的常见问题，在工作生活各个领域有重要意义。介绍多种排序算法的特点，分析经典冒泡排序算法的原理，并从排序效率的角度提出LSort字符算法，该算法通过建立一个有序序列并进行排序，有效提高排序操作效率。 　　关键词：排序；算法；有序序列 　　DOIDOI：10.11907/rjdk.161482 　　中图分类号：TP312 　　文献标识码：A文章编号文章编号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；in；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） 　　*（