怎樣只用位運算實現高效的排序算法？

前言如果你準備看這篇文章，我就當你是懂快速排序算法原理的。下面是我在2018年10月3日想到的基于二進制位運算對正整數進行的一種快速排序算法，目前的代碼只能對正整數進行有效的排序，當然，稍微修改一下就可以支持負數的排序了。后面會給出我用Julia語言實現的沒有經過優化的代碼和一些測試結果。如果您對此能有什么改進或者能幫嗎優化一下代碼，請告知我一下，我會非常感謝您。下面是此算法的思想和原理。2是一個神奇的數字，可以用來做很多東西，二叉樹，二分搜索，快速冪算法以及很多分治算法都是在2這個神奇的數字的幫助才能達到他們的優雅和高效率。利用二進制，我們也可以進行快速排序。如果要對一列數字進行排序，你會怎樣去做呢？學過快速排序的同學應該會立即想到快速排序。先選一個數字，然后從兩邊開始，分別把小于它的數字交換到它的左邊，把大于它的數字交換到它右邊，完成這一過程，其右邊的數字全體大于等于它，左邊的數字全部小于等于它。然后分別對其左邊和右邊遞歸地運用此方法（快速排序）進行排序，當排序的長度小于2時，遞歸過程完成了，這一列數字也就變成有序的了。這種最基本的快排算法是不是也散發著二分的思想？如果它再二一點會怎樣？那就是我下面想要談論的基于二進制的快速排序算法了。哈哈，我給它加入了二進制。其實除開二進制的位運算，這個算法跟快速排序算法基本上是一樣的，所以我暫且稱之為BQuickSort（Binary or Bit）。算法的基本思想對每一個二進制位，把該位是1的數字劃分到右邊，是0的劃分到左邊。高位優先，通過交換來進行。實現在算法的實現上我采用了按位與運算，先用的時間復雜度求出其中最大的數字，然后對最大的數字進行一次簡單的flp2運算（把其二進制最高位之外的bit全部置0，這里的最高位并非64或32等，而是左邊第一個不為0的bit），獲得一個為2的n次冪的整數變量，我們暫且把它命名為shift。每一次所做的就是用這個shift與一個要排序的區間段進行按位與運算運算，將右邊運算結果為0的數字同左邊運算結果不為0的數字進行交換，并返回交換之后的分割位置。然后遞歸地將同樣的算法運用于分割位置的左邊和右邊，只需將shift右移一位即可。遞歸結束的條件是區間寬度小于1或者shift等于0。對于一次部分排序，我寫了兩個函數，一個像快速排序那樣從兩邊向中間行進，是不穩定的算法，另一個只從左邊行進，應該是穩定的算法。演示接下來我將演示對下列所示的整數序列進行的BQuickSort。 在這里最大的數字是10(二進制為1010)，通過對10進行flp2運算，我們將獲得一個數字8（二進制為1000）。將shift（這里為8）同每一個數字進行按位與運算并把運算結果不為0的數字交換到右邊，最后我們返回一個整數索引10，它記錄了一次排序之后的分割線（分割線左邊的數字都小于8，同8進行按位與運算為0；右邊的數字都大于等于8，同8進行按位與運算不為0）。 鑒于分割線及其右邊的數字都大于左邊的數字，下面值演示對左邊的數字進行的排序，同樣的方法適用于右邊。將shift右移一位（結果為4），然后與分割線左邊的數字（前9個）進行與上面一樣的部分排序操作，我們將得到下面這張圖所示的序列。 再對前3個數字進行shift為2的部分排序，1將被交換到左邊，此時前3個數已經有序，但是遞歸其實尚未結束，下一次遞歸是shift為1的一次部分排序。繼續對第4~9個數字執行同樣的部分排序，最后我們將會得到前九個數字的有序排列。之后再對第10~12個數字進行同樣的部分排序，我們就會得到一個所有數字的有序排列。 算法實現代碼

[/code][size=5]測試代碼[/size][code]復制代碼

一些測試結果[code][/code]