一种节省空间的排序算法  

Space-Minimized Sorting Algorithm

作　　者：方同祝[1] 胡正国[1] 田铮[1] 金文凯[1] 

机构地区：[1]西北工业大学计算机工程与科学系,陕西西安710072

出　　处：《小型微型计算机系统》2005年第7期1200-1201,共2页Journal of Chinese Computer Systems

基　　金：国家自然科学基金(60375003)资助;航空基金(03153059)资助

摘　　要：目前报道的一些排序算法,空间复杂度都比较大.提出了一种改进其空间复杂度的方法,其特点是算法简单、稳定,时间复杂度为O(n2),空间复杂度为2n,达到下界.与传统的排序算法用变量与变量比较的思路不同,本文提出的是一种用变量与其分布区间进行比较的新思路.本算法特别适合那些范围确定且分布基本均匀的待排数据,也适合一般数据对象的排序.A new,simple and stable sorting algorithm,which reduces space complexity to the theoretically possible minimum, is proposed.The proposed algorithm has time complexity O(n 2) and space complexity 2n.The difference of idea between our method and the current available algorithms is that ours compares each variable with the distributing intervals,but previous sorting algorithms compare one variable with another.Experiments demonstratc the proposed algorithm is suitable for sorting general data, especially for sorting the data whose bound is given and distribution is basically even.

关 键 词：排序 时间复杂度 空间复杂度 

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