一种节省空间的排序算法

目前报道的一些排序算法，空间复杂度都比较大．提出了一种改进其空间复杂度的方法，其特点是算法简单、稳定，时间复杂度为O(n^2)，空间复杂度为2n，达到下界．与传统的排序算法用变量与变量比较的思路不同，本文提出的是一种用变量与其分布区间进行比较的新思路．本算法特别适合那些范围确定且分布基本均匀的待排数据，也适合一般数据对象的排序．

Space-Minimized Sorting Algorithm

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.