移位排序算法--从赛跑想到的

说到排序，可能你能说出一大堆，什么冒泡，快速，插入，希尔...说实话，我能轻易写出那些算法，但是总觉得没有什么意义，人的脑子里净装一些书上的东 西，还不如去当图书馆管理员呢？于是我就从最简单的排序算法开始自己实现一个书上没有的，也可能书上有只是我没有看到罢了，不管怎么说，练练。这个算法可能时间复杂度很高，也可能空间复杂度使得根本不值得用，也可能有漏洞，但是有什么关系呢？我又不是大师，只当娱乐了。说到排序，办法无非就是比较，一个一 个数比较，算法的优劣只是比较时的技巧不同，只要比较就有竞争，有竞争就有胜利者，比较和比赛在这个意义上是相同的，程序设计者要时刻关注人世间发生的每一件事，这是我的信条。
就说赛跑这种比赛吧，大家在同一起跑线，然后发令枪一响，所有参赛者同时起跑，谁第一个到达终点就是第一名，然后第二名，第三名，顺序就这么排好了，如果在排序算法中也这么干可不可以呢？几个要排序的数同时开始比较，同时“起跑”，不用它们之间一一比较，而是存在一个统一的对大家都公平的“终点线”，以它 们越过终点线的顺序为最终顺序。当然可以了，把奔跑抽象成移位，把终点线抽象成确定的位不就可以了吗？实际上就是这样的，我们使所有参与排序的数字同时向右移位，比如排序32位整数，我们把终点线设置为0XFFFFFFFE，就是第32位为1，其余低位都是0，然后让所有数一位一位向右移，谁第一个和终点线“与”操作后不为0就说明它首先有为1的位移到了第32位，那么它就是最大的数。如果有很多数都同样的移动到了最右边并且和终点线“与”操作不为0，那 么就说明需要对它们“加赛”，办法和前面比赛相同，只是不再从头开始移位了，而是从它们相等的位的下一位再开始，直到区分出胜负或者移完了整个32位。
上述方法在逻辑上很简单，也很合理，但是软件实现上要达到高效和谐却有很大困难，毕竟冯诺依曼机器不是并行机，它很擅长一步一步做事，而不擅长大家一起来，要想高效实现上述赛跑模型，我觉得用向量机更合适，在我们的标量机上，加上时间不充裕，我也只能做出一个拙劣低效的实现。其实移位是一个很重要的运 算，一些机器上的CRC校验就是用移位进行运算的，和上面的赛跑模型差不多，移位排序用硬件实现效率要高得多，毕竟那是硬件的强项，硬件只认识“位”。在 软件上，只能说可以实现，因为硬件能实现的过程通过软件都可以模拟，重点就是认识到运算逻辑，然后写出程序。下面给出我的实现（java版本）：

/*

*iMaxTypeLength--要排序的数据类型的长度

*iDataLength --排序数组的长度

*iStart --移位开始的位置（相对于当前数，从右向左计数）

*iArrayToSort --要排序的数组

*last --进入比赛的元素索引

*iIndexResult --结果排序索引

*/

public static void BitSort( int iMaxTypeLength, int iDataLength, int iStart, int iArrayToSort[],int last[], int iIndexResult[])

{

int[] index = new int[iDataLength];

for (int i = 0;i<idatalength><p> {</p> <p> index[i] = -1;</p> <p> }</p> <p> for (int i = iStart; i </p> <p> {</p> <p> int j = 0,tx = 0,k=0;//tx为当前比赛胜出者索引，k为参加加赛者的数目</p> <p> for (j = 0; j </p> <p> {</p> <p> if ( iArrayToSort[j] != 0 &amp;&amp; last[j] == j ) </p> <p> {</p> <p> if (((iArrayToSort[j] </p> <p> {</p> <p> iArrayToSort[j] = (iArrayToSort[j] </p> <p> tx = j;</p> <p> index[j] = j; //计入加赛数组</p> <p> k++; //递增加赛者数目</p> <p> }</p> <p> }</p> <p> }</p> <p> if ( k &gt; 1 ) //超过一个数通过，必须加赛</p> <p> {</p> <p> BitSort( iMaxTypeLength-i, iDataLength, 1, iArrayToSort, index, iIndexResult ); //加赛，需要加赛的都计入了index数组</p> <p> }</p> <p> else if ( k == 1 ) //如果就一个数通过，那么就不必加赛了，输出胜利者</p> <p> { </p> <p> iIndexResult[ppp++] = tx; //计入最终的索引结果</p> <p> iArrayToSort[tx] = 0; //将该位置清零，表示它已经比赛完了</p> <p> last[tx] = -1; //同上</p> <p> }</p> <p> }</p> <p> for ( int i = 0; i<idatalength i><p> {</p> <p> if ( last[i] != -1 &amp;&amp; iArrayToSort[i] != 0 )</p> <p> {</p> <p> iIndexResult[ppp++] = i; //计入最终的索引结果</p> <p> iArrayToSort[i] = 0; //将该位置清零,表示它已经比赛完了</p> <p> last[i] = -1; //同上</p> <p> }</p> <p> }</p> <p>}</p> <p>看 了代码后很多人包括我自己都在问，这么多的for循环和毫不确定的递归，慢到不知哪里去了。这就是我说的该实现的拙劣，事实上，在拥有特定硬件的情况下， 比如说向量机或者说支持DX10的显卡，每一个for循环都是可以让硬件并行执行的，因此循环多并不是关键，关键是运算的逻辑，我们可以看到，每次比赛，不管是正式比赛还是加赛，都是一通到底的，即使用到了递归也没有回溯，只要进入了BitSort函数，非要区分出胜负不可，我们可以通过代码看到最后的那个for循环就是将本轮比赛或者加赛的失败者输出，这就是没有回溯的原因。 <br>当我完成这段代码并且理清了逻辑后，我会很不屑的认为，这太失败了，基于位的radix树也是按位比较的，而且按位的radix本质上也是一棵排序二叉 树，这种移位排序到底比按位的radix树好在哪里？想了又想终于发现，按位radix树之所以是排序的，是因为它完全依赖树结点的插入，插入保证了结果是排序的二叉树，那么看看插入，涉及到回溯，平衡性，而且插入本身就是拿要插入的数字与树中的节点数字相比较，本质上还是比较，和传统的那些冒泡排序之类 是一样的。硬件会实现位并行运算但是很难实现数字并行比较，就算实现了也很没有意义，因为所有运算的最终都要归结为位运算，一个运算是否值得硬件实现首要考虑的是所有运算的交集而不是并集。因此移位排序在这点上是优秀的，在模型上是清晰的，谁都知道赛跑怎么进行，你我就经历过，但是啤酒泡泡从瓶底冒上来也 只有喝啤酒的人才知道，难道你非要抬杠说可乐泡泡或是茶水泡泡吗？总之类似于赛跑的方式更加容易被理解。 <br>我写这篇文章的目的不是仅仅为了说明一个小小的算法，而是为了说明位运算的重要性，我读过linux内核和很多开源的应用程序代码，发现用位运算解决问题 的方法都是高效的解决方法，当你真正和机器成为朋友，你就不觉得二进制的0和1比十进制数更难懂了。好了，来看看那个排序怎么用吧：</p> <p>public class Sort</p> <p>{</p> <p> static int ppp = 0;</p> <p> public static void BitSort( int iMaxTypeLength, int iDataLength, int iStart, int iArrayToSort[],int last[], int </p> <p>iIndexResult[]){.../*省略，见上面*/}</p> <p>}</p> <p>public class TestBitSort</p> <p>{</p> <p> static int a[] = { 3, 8, 14, 11, 1, 9, 4, 12, 2, 15, 6, 7, 10, 5, 13 };</p> <p> public static void main(String[] args)throws Exception</p> <p> {</p> <p> int ide[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};//参加比赛者，初始情况全部参加</p> <p> int b[] = { 3, 8, 14, 11, 1, 9, 4, 12, 2, 15, 6, 7, 10, 5, 13 }; //创建一份a的副本</p> <p> int[] IndexResult = new int[15];</p> <p> BitSort(8, 15, 0, a, ide, IndexResult);</p> <p> for (int i = 0;i </p> <p> {</p> <p> System.out.println( bb[IndexResult[i]]); //输出排序的结果</p> <p> }</p> <p> }</p> <p>}</p> <p>其实我们最后将待排序数组的排序索引输出而不是直接将排序数组输出也是好理解的，在真正比赛中，裁判也是按号计分的，而不是按照参加比赛的人，回归我们的算法，待排序的数组类型多种多样，而排序的索引都是整数，因此我们就可以将代码写得更具有一般性。</p> </idatalength></p></idatalength>