| 摘要: |
| 通过分析任意输入的n个数据的组成特性,设计一种O(n+nlog2m)时间复杂度的排序算法,m为原始输入数据序列中有序/逆有序的子序列个数,1≤m≤n/2。此排序算法的时间复杂性结果与输入数据的概率分布假设无关 |
| 关键词: 排序 算法复杂性 数据置换 |
| DOI： |
| 投稿时间：2002-06-16 |
| 基金项目:国家"十五"863计划课题(2001A111004)的资助项目 |
|
| A Sorting Algorithm with O(n+nlog2m) Time Complexity |
|
Lu Xiaoming, Zhong Cheng
|
| (College of Computer and Information Engineering, Guangxi University, Nanning, 530004) |
| Abstract: |
| By analyzing the characteristics of the n given input data,a sorting algorithm with O(n+nlog2m) 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. |
| Key words: sorting algorithm complexity data swap |
