文章来自达梦技术社区http://bbs.dameng.com/

　　1、 线性排序算法原理

　　32位整数排序算法的原型是基于不等式K+1>K>K-1的，该式子对于任何K值都成立。那么如果有一个坐标，长度为Kn，每个Kx都可以映射到这个坐标轴的相应点上。这样一来，就可以得到一系列自然次序排列的点。现在针对具体的例子来看看这个算法的具体内容，假设有一个数例：9, 6, 3 与 7。取第一个数（9），将它从坐标轴原点开始向右移动9个普通单元并标记这个点。然后，取下一个数（6）并重复操作等。这些操作的结果如图1所示。

　　现在，从左向右沿坐标线移动， 并将没有标记的所有点都丢弃掉（或者突出显示经过标记的点）。于是，得到一系列按升序排列的数。如果从右往左沿坐标线移动，那么将得到一系列按降序排列的数。

　　这里有一点最令人感兴趣：不管数是如何给定的，对它们进行排序所需要的操作次数将总是等于N+VAL_N，其中N是待排序的数据个数，而VAL_N是数据可能取值的最大个数。由于VAL_N是个常数，因此可以将它从估算算法复杂性公式中去掉。之后，这个公式就变成为O(N)了。

　　可能读者已经注意到这种排序算法的弱点了。性能增益是以牺牲内存为代价的。线性排序算法在内存消耗方面的开销很大。下面是关的一些估算值。如表1所示：

　　虽然存在这样的弱点，但是却仍然盖不住它的优点，在算法分析和设计中，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间需求常常是决定算法在实际中是否真正有效的决定性因素。用它跟快速排序算法比较，线性排序算法时间复杂度为O(n)，而快速排序算法平均需要O(nlgn)次操作，并且在最坏的情况下需要O(m2)次操作。
 针对上面线性排序算法的弱点，如果要排序的数数值范围在0 到 2147483647，那么至少需要8GB的内存，需要的内存在现实中将是不可能提供的；并且也不能排序正数跟负数相混合的情况，我们必须对这个算法加以改进，以满足现实应用中的需求。

2、 改进后的线性排序算法

2.1  改进思想：
　　在日常应用程序中，整数最常用的数值一般都处在百万以内，而构造一百万个坐标点的坐标，需要大约4M的内存，这在现在的计算机内存配置上完全是可行的。于是我们专门针对这种特点对原型改造，将4字节的32位整数按位分类排序（4字节的整数有32位），把32位分成两段，前12位为一段，后20位为第二段，用十六进制来表示，既0XFFF00000（高12位）和0X000FFFFF（低20位）。分段以后我们在影射处在0到1048576的整数时，就可以按原型的方法直接影射在1048576个坐标点的坐标上，对大于1048576的值，我们会继续对它的低20位分段排序，这种处理方式极好地保证了最常用的整数值的排序效率。
2.2 影射坐标定义：
　　一个32位的整数，它能表示值的区间为 -2147483648 到 2147483647，按照改进思相，我们把这个区间分为三段：
　　1) 0XFFF00000 到 0XFFFFFFFF 区间，代表的值为期 -1048576 到 -1，它们的高十二位值都是相同的，为 0XFFF，在排序的时候我们把它们归为一类，可以影射到代表负数的 1048576 个坐标点的坐标上，我们把这个坐标设为 a 坐标
　　2) 0X00000000 到 0X000FFFFF 区间，代表的值为 0 到 1048576，它们的高十二位值也是相同的，为 0X000,也把它们归为一类，可以影射到代表正数的 1048576 个坐标点的坐标上，我们把这个坐标设为 b 坐标
　　3) 剩余的两个区间为 0X80000000 到 0XFFEFFFFF 区间和 0X001FFFFF 到 0x7FFFFFFF 区间，它们分别表示的范围是 -2147483648到 -1048577 和1048577 到2147483647, 处在这个区间的值，我们先它们按各自的前 12 位的值影射到 4096 个坐标点的坐标上（0XFFF 转为十进制为 4096），我们把这个坐标设为 c 坐标
　　4) 对于处在0X80000000 到 0XFFEFFFFF 区间和 0X001FFFFF 到 0x7FFFFFFF 区间的情况，我们将把它们按高 12 位分类以后，不能立即分析出其大小的（一个坐标点上影射有两个以上的整数），再对其低 20 位分段，进行第二次影射。第一段为低20位的前12位，坐标点数为4096个，我们把这个坐标设为 d 坐标
　　5) 对处在0X80000000 到 0XFFEFFFFF 区间和 0X001FFFFF 到 0x7FFFFFFF 区间的情况，经过第二次影射以后还不能立即区分大小的，再对它们的低20位的低8位进行影射到256个坐标点的坐标上，我们把这个坐标设为 e 坐标
　　由上面可以看出，我们总共定义了5个坐标，a，b，c三个用来影射不同区间的整数，分别是0XFFF00000 到 0XFFFFFFFF(a坐标)、0X00000000 到 0X000FFFFF(b坐标)、0X80000000 到 0XFFEFFFFF 和 0X001FFFFF 到 0x7FFFFFFF(c坐标)；d，e这两个是用来帮助分类c坐标上的整数

2.3 影射算法流程：
　　a) 扫描整个要排序的整数，依次取出一个整数 x
　　b) 执行与操作 y = x & 0XFFF00000，再执行移位操作，把 y 向右移 20 位, y = y>>20，便获得这个整数的高 12 值
　　c) 判断得到的 y 是否为 0， 如果是，则影射 x 到 b 坐标上，如果不是，则再判断 y 值是否为 0xFFF，如果是，则影射 x 到 a 坐标上，否则影再判断 y 值是否大于2048， 如果是则表示 x 为0X80000000 到 0XFFEFFFFF 区间的负数，把 y 减去 2048 后影射到 c 坐标上，否则表示 x 为0X001FFFFF 到 0x7FFFFFFF 区间正数，把 y 加上 2048后影射到 c 坐标上。影射以后把该坐标点上的统计该坐标点拥有整数个数的变量加一
　　d) 所有待排序整数影射完成，所有区间的整数就会分类存放在坐标a，b，c上，然后我们似次遍历这三个坐标来输出它们，在正序排序时，我们先输出c坐标上0到2047的坐标点上的值，因这这段区间存放的是，2147483648到 -1048577之间的负整数
　　e) 依次判断c坐标从0到2046坐标点上各坐标点上整数的个数，如果整数个数小于n(实验对比下来，n取值小于等于200的时候，用快速排序算法对该坐标上的整数比再次影射坐标排序来得快)，我们可以使用快速排序法来排序这个坐标点上的几个整数，否则，我们就再次对这些整数进行第二次扫描，把它们按整数的低20位的高12值影射到辅坐标d上。执行操作：
　　1) 依次读取c坐标的i（0≤i≤2046）坐标点上的整数 x，然后取得其低20位的高12值y（y = x  & 0X000FFFFF >> 8）
　　2) 把x按y值射到坐标d上，并把统计该坐标点拥有整数个数的变量加一
　　3) 当i坐标点上所有整数被第二次影射完必以后，我们按从头到尾的顺序扫描坐标d，依次判断各个坐标点上整数的个数，如果整数各数小于n(同上)，我们可以使用快速排序法来排序这个坐标点上的几个整数，否则，我们就再次对这些整数进行第三次扫描，把它们按整数的低20位的低8位值影射到辅坐标e上。执行操作：
　　1. 依次读取d坐标的i（0≤i≤4095）坐标点上的整数 x，然后取得其低20位的低8值y（y = x  & 0X000000FF）
　　2. 把x按y值射到坐标e上（不需要统计变量，原因见下面第3点）
　　3. 当i坐标点上所有整数被第三次影射完必以后，我们按从头到尾的顺序扫描坐标e，依次输出各个坐标点上的整数索引到存放索引的缓冲区中（如果坐标e上某个坐标上存在多个整数，那这些整数的值一定是相等的，不用再排序，因为它们的高12位相同，低20位的高12相同，低20位的低8位相同）
　　f) 当到达c坐标的2047坐标点时，这上面应该存放的是-1048576 到 -1这个区间的整数，而这个区间的整数我们用了专门一个坐标a来存放，于是我们按从头到尾的顺序扫描坐标a，依次输出各个坐标点上的整数索引到存放索引的缓冲区中（如果坐标a上某个坐标上存在多个整数，那这些整数的值一定是相等的，不用再排序，因为它们的高12位相同，低20位也相同）
　　g) 当到达c坐标的2048坐标点时，这上面应该存放的是0到1048576这个区间的整数，而这个区间的整数我们用了专门一个坐标b来存放，于是我们按从头到尾的顺序扫描坐标b，依次输出各个坐标点上的整数索引到存放索引的缓冲区中（如果坐标b上某个坐标上存在多个整数，那这些整数的值一定是相等的，不用再排序，因为它们的高12位相同，低20位也相同）
　　h) 最后一步我们要扫描坐标c的2049到4095这个区间，这段区间存放的是大于1048576的正整数，扫描输出的方法跟扫描输出小于-1048576的负整数一样，这里不再重述
　　i) 当c坐标被整个遍历完以后，我们就会在输出索引缓冲区中得到一条整数从小到大排序好的索引序列

2.4　影射坐标图例：
　　为了方便理解上面的影射思想，我们在下面图解了一下影射六个整数高12位到坐标c上的情景，整数是用16进制表示

图2  整数高12位到坐标c上的情景

注：上图 c 坐标为了影射表示方便，没有把整数高12位的值加2048后再影射到 c 坐标上

3、 多CPU的支持
3.1 性能提升空间
　　经过实际的试验和分析，在改进后的算法实现中，花费的时间主要集中在输出第一次扫坐后的坐标 a，b，c 上！因为我们坐标点上的整数用的是单向链表的形式组织的，分类时不断的把整数的索引描述结点不断插入到对应的坐标点的链表上；因此，在遍历各个坐标点的链表时将会对内存进行随机访问，这就会造成CPU高速缓存的缺页，CPU将会遭受延时处罚，严重影响了整数排序算法的性能，于是就想到了用多个CPU按坐标点顺序分段输出 a，b，c 三个坐标的想法，以便减少单个CPU被延时处罚的次数，达到算法性能提升的目的。
3.2 影射坐标定义
　 1) 共用坐标：
　　共用坐标是用来存放第一次扫描后的整数分类情况，从第二节我们可以了解到 a，b，c 这三个坐标就是共用坐标
　 2) 每个CPU辅助坐标的定义：
　　在第二节中我们可以了解到，要输出c坐标上的整数，我们需要用到 d 和 e 坐标来继续分类整数，于是我们需要为每个CPU定义两个辅助坐标 d 和 e
3.2 分段规则
　　假如要用4个CPU排序200万个整数，那么在理想的情况下，分段后每个CPU处理的整数个数应该为50万个（200万/4 = 50万），实际情况中并不能完全保证按这一比一的比例来分配任务，因为任务分配是按坐标点而不是整数个数，我们不可能会把一个坐标点上的链表分段后交给多个CPU处理。也就是说，如果排序的200万个整数值都是相等的，那这200万个整数将会存在同一个坐标的同一个坐标点上，那么我们在分段时，就把这个坐标点只分给一个CPU来输出（大家不用担心这种情况会影响算法性能，因这链表上的各个节点处在的内存空间是连续的，而CPU访问连续的内存空间将会非常快）。
 分段方法：
1) 按包含整数大小的顺序把 a，b，c 三个坐标分四类：
　1. c坐标的0-2046区间（x≤-1048576）
　2. a坐标（-1048576≤x≤0）
　3. b坐标（0≤x≤1048576）
　4. c坐标的2049-4095区间（1048576≤x）
 2) 定义4个变量用来存放分段的信息：unsigned int start_pos, start_type, start_output_pos, end_pos, end_type, end_output_pos；它们分别代表开始坐标的起始位置，开始扫描坐标的类型（四类坐标区间的那一类），输出索引缓冲区的开始位置偏移量，结束坐标的位置，结束坐标的类型，输出索引缓冲区的结束位置偏移量
 3) 计算每个CPU理想情况下的终止输出索引时在索引输出缓冲区中的偏移量(end_output_pos = num/cpu_n + num/cpu_n * i，其中num为整数的总个数，cpu_n为CPU的个数，i代表当前CPU是第几个CPU)，沿用那个200万个整数的例子，按此方法计算后，第一个CPU输出索引终止偏移量为50万，第二个CPU为 100 万，第三个为150万，第四个为200万
 4) 按坐标分类的顺序，设置第一个CPU的起始位置为第1类坐标的第0个坐标点，然后依次扫描坐标累加每个坐标点上整数的个数，如果累加的个数已经大于第一个CPU理想情况下输出索引的编移量时，那么，把这一坐标设置为它的终止位置，保存该坐标的类型和当前坐标的位置，并重置它人输出索引偏移量为累加到的整数个数值
 5) 当要设置第二个CPU的起始和终止扫描位置时，它就会从把第一个CPU的终止坐标的下一个坐标点当作自己的起始坐标点，坐标类型拷贝第一个CPU终止的坐标类型，累加的整数个数初始化为第一个CPU的输出索个编移量；然后按照第一个CPU的方寻找属于自己的终止位置
 6) 设置接下去几个CPU的起始和终止扫描位置方法类似第二个CPU的设置方法
3.2 分段扫描流程
　a) 扫描整个待排数的整数数组，把它们分类到坐标 a，c，d 上
　b) 取得当前系统CPU的个数 cpu_n
　c) 创建 cpu_n – 1 个新线程(因为当前线程也会参于后面的分段排序，所以只需要创建 cpu_n – 1个新线程)
　d) 当前线程在创建完其它线程后，直接从第一个坐标的第0个坐标点开始按第二节的影射算法排序，只是在排序过程中，当要读取下一个坐标点时，先要判断累加处理的整数各数是否大于等于它的索引终止偏移量，如果不是，则继续处理，否则，在处理完当前点以后，就立即停止处理，等待其它线程完成各自己的任务后再返回
　e) 如果被创建的线程属于第二个CPU，那么它首先要按上一小节分段规则的思想查找第一个CPU处理时的终止位置，通过它再确定自己的起始位置，接着按分段规则查找自己的终止位置，最后按影射算排序算法排序和输出自己任务段的整数
　f) 如果被创建的线程属于第二个后面的几个CPU，那么，它们首先停阻塞在当前位置，直到自己上一个CPU确定了终止位置后，它才能设置自己的开始位置和查找自己的终止位置，最后按影射算排序算法排序和输出自己任务段的整数

4、 TOP N 的实现
　　现实应用中还存在一种情况，那就是虽然要排序成百上千万个整数，但应用只需要用到成百上千万个整数的前N个整数（比如数据库中的SELECT TOP N语句）。这种情况下那么就没有必要把所有整数排序完才返回，只要在索引输出时增加监视，输入索引个数达到N时就可以返回了，这种情况也可以提升性能很多倍。
在上面多CPU的线性排序中，我们只需要轻松更改每个CPU输出索引缓冲区终止的偏移量就能达到这个目的。

5、 算法的复杂度分析
　5.1  时间复杂度
　在排序从-1048576≤x≤1048576区间的整数时，每个整数只会被影射一次，所以它的时间复杂度为O(N)
　在排序x≤-1048576和1048576≤x区间的整数时，在最坏的情况下，每个整数会被影射三次，所以它的时间复杂度为O(3N)。
　在实际应用当中，x≤-1048576和1048576≤x区间会存在很多整数在第一次或是第二次影射后（在坐标上只存在一个或是两个整数的情况），就可以立即输出它的索引了，不需要再次影射。  从时间复杂度上看，该算法理论上是非常迅速的，但实际的性能受到了链表访问操作的影响，CPU在整个算法里花了大量的时间来加载随机访问的内存，导致该算法达不到理论上的速度
5.2  空间复杂度  该算法中，总共有3部分需要消耗内存：   1. 最耗费内存空间的部分是将为排元素生成一个索引描术结构，如果要排序n个整数，那么我们需要的内存数=　　(整数索引+整数值+存放下一个索引指针空间)*整数个数=(sizeof(int)+sizeof(int) +sizeof(void*))*n;以200万个待排整数为例，这部分需求的内存数为(4+4+4)*2000000=24000000(约23M 的内存)
2. 坐标映射需求的内存=坐标点个数*每个坐标点使用内存=坐标点个数* (坐标元素个数记数空间+坐标上元素链表头指针存放空间)=坐标点个数*(4+4)
　a 坐标：1048576*8 = 8M
　b 坐标：1048576*8 = 8M
　c 坐标：4096*8=32K
　d 坐标：4096*8=32K
　e 坐标：256*8=1K
3. 排序时输入的整数数组以及索引输出缓冲区，如果要排序n个整数，那么我们需要的内存数=n*单个整数存放空间 + n*单个索引值存放空间= n*sizeof(int) + n*sizeof(int)，以200万条为例，这部分需要 2000000*(4+4)= 16000000(约16M)
从以上可以得到，在n个CPU的系统下面，算法需要的内存总数为：8M + 8M + 32K + (32K + 1K)*n + 索引描述部分 + 输入输出部分。以200万为例，总共约55M的内存

6、 性能测试
　下面是该算法在单CPU的情况下跟快速排序算法的性能对比（快速排序调用的是C库中的qsort函数）,测试运行环境为操作系统Windows XP, P4 2.6G HZ ,内存DDR400 1G，硬盘160G(7200转/分)。

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/23392679/viewspace-627938/，如需转载，请注明出处，否则将追究法律责任。