一种改进的鸡尾酒排序算法  

An improved cocktail sorting algorithm

作　　者：张凡 殷锋[1] 苗潇文 张细凯 ZHANG Fan;YIN Feng;MIAO Xiao-wen;ZHANG Xi-kai(School of Computer Science and Technology,Southwest Minzu University,Key Laboratory of Computer System of the State Ethnic Affairs Commission,Chengdu 610041,China)

机构地区：[1]西南民族大学计算机科学与技术学院,计算机系统国家民委重点实验室,四川成都610041

出　　处：《西南民族大学学报（自然科学版）》2021年第1期60-65,共6页Journal of Southwest Minzu University(Natural Science Edition)

基　　金：国家社会科学基金项目(16ZDA166);四川省科技项目(14ZC1767);西南民族大学研究生创新型科研项目(CX2020SP72)。

摘　　要：鸡尾酒算法是一种基于双向遍历的排序算法,相比于传统的冒泡排序算法在排序效率上有一定的提高,但仍存在大量的重复数据比较以及对初始输入序列随机度过于敏感等问题.针对上述问题,引入了一种鸡尾酒排序算法的改进算法(Trigger-Conditional Cocktail Sort Algorithm,简称T-CCS).通过记录排序过程中每次发生数据交换的位置来缩小遍历区间,并以发生数据交换作为分段逆向遍历的启动条件,减少重复的数据比较.实验结果表明,T-CCS算法在不同规模输入数据的排序处理中均有较好表现,其排序效率相比于原算法提高了20%;同时,该算法受初始输入序列随机度的影响也相对低于传统的鸡尾酒排序算法.The cocktail algorithm is a sorting algorithm based on two-way traversal. Compared with the traditional bubble sorting algorithm, it has a certain improvement in sorting efficiency. However, there are still a large number of repeated data comparisons and the sensitivity to the initial input sequence randomly. In response to the above problems, an improved cocktail sorting algorithm(Trigger-Conditional Cocktail Sort Algorithm, T-CCS for short) is introduced. By recording the location of each data exchange in the sorting process, the traversal interval is narrowed, and the data exchange is used as the starting condition for the segmented reverse traversal to reduce repeated data comparisons. The experimental results showed that the T-CCS algorithm performed well in the sorting processing of input data of different scales, and its sorting efficiency increased by 20% compared with the original algorithm;at the same time, the algorithm was less affected by the randomness of the initial input sequence than the traditional cocktail sorting algorithm.

关 键 词：排序算法 鸡尾酒算法 遍历区间 序列随机度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]