一种基于动态交换的计数排序算法  

A Counting Sort Algorithm Based on Dynamic Exchange

作　　者：兰洋[1] 尤磊[1,2] 

机构地区：[1]信阳师范学院计算机与信息技术学院,河南信阳464000 [2]中国林业科学研究院资源信息研究所,北京100091

出　　处：《信阳师范学院学报（自然科学版）》2015年第2期279-282,共4页Journal of Xinyang Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(31470641;61163017;61202194);河南省基础与前沿技术研究计划项目(122300410372);河南省教育厅科学技术研究重点项目(12B520051;14A520033);河南省自然科学基金项目(142300410351);河南省教育厅自然科学研究计划项目(2011A520039);信阳师范学院青年基金项目

摘　　要：提出一种动态交换的策略,对一个元素计数后,根据计数值的大小将元素移动到序列的合适位置,使得算法在每运算一个元素后,元素间的排列都是有序的,计数值大的元素位于序列的前端,从而有效地减少了查询时间.分析了算法的时间及空间复杂度,并通过实验验证了算法的实时性与高效性.To ensure elements were in the proper position after each element was calculated, a dynamic exchange strategy was presented to exchange the element＇ s position according to the element＇ s counting value. The element hav- ing the bigger counting value was set to the frontier position, which reduces effectively the query time. The complexity of time and space were also analyzed and the real-time and efficiency were verified through the experiment.

关 键 词：排序算法 计数 动态交换 容器 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]