| 一种针对特定数据的高效排序算法--算法复杂度为O （N.. |
 |
| 作者是 Administrator | |
| 2008-04-23 07:45:03 | |
|
该数据序列具有以下特点: 1.都是正整数;2.该序列中所有元素都互不重复;3.该序列跨度范围相对较小. 举个例子:2 12 4 15 9 28就是这样一组序列; 4 12 4 1000000 16该序列就不符合上述特点中的第2和第三点 这里的排序算法主要用到了bitmap的数据结构: 如数据序列:1 2 3 5 8 13的相对应的bitmap就是:0 1 1 1 0 1 0 0 1 0 0 0 0 1 即:该数据序列最大数值是几就可以构造一个具有相应位数的0,1位图序列,在位图序列中,序列中所有数据项值的相应位表示为1,其他为0. 设待排数据序列为数组array[m],且该序列中最大数据项为n.则相应的位图序列为bit[n]; 因此排序步骤是: 1.初始化一个位图数组,并将其中每一位设为0. for(i=0; i<n; i++) bit[i]=0; 2.将数据序列中相应数据项位置为1. for(i=0; i<m; i++) bit[array[i]]=1; 3.若位图数组中某项为1,则打印相应的下标. for(i=0; i<n; i++) if(bit[i]==1) printf("%d ", i); 当然,这里的数据项都是完全满足上述三条特点,其实我们也可以通过其他方法进行转化以达到上述要求:如若序列中存在负数,我们可以对该序列都加上同一个正数使序列都变成正数. 等等.该算法的时间复杂度为O（N），这是一种典型的通过空间换时间的方法。当跨度不大的时候，所需额外空间也是很少的。 |
|
| 最近更新 ( 2008-04-23 07:45:03 ) |
