一种O(n+nlog_2m)时间复杂度的排序算法  

A Sorting Algorithm with O(n+nlog_2m) Time Complexity

作　　者：鲁晓明[1] 钟诚[1] 

机构地区：[1]广西大学计算机与信息工程学院,南宁530004

出　　处：《广西科学院学报》2002年第4期151-154,共4页Journal of Guangxi Academy of Sciences

基　　金：国家"十五"863计划课题 (2 0 0 1A1110 0 4)的资助项目

摘　　要：通过分析任意输入的 n个数据的组成特性 ,设计一种 O( n +nlog2 m)时间复杂度的排序算法 ,m为原始输入数据序列中有序 /逆有序的子序列个数 ,1≤ m≤ n/2。By analyzing the characteristics of the n given input data,a sorting algorithm with O(n+n log 2 m) time complexity is presented,where m is the number of the sorted or conversely sorted sub-sequences in the original input sequence,1≤m≤n/2.The time complexity result is independent of the hypothesis of the probability distribution of the input data.

关 键 词：O(n+nlog2m)时间复杂度 排序算法 数据置换 计算机算法 概率分布 数据交换 

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