前言

如果你準(zhǔn)備看這篇文章，我就當(dāng)你是懂快速排序算法原理的。

下面是我在2018年10月3日想到的基于二進(jìn)制位運(yùn)算對正整數(shù)進(jìn)行的一種快速排序算法，目前的代碼只能對正整數(shù)進(jìn)行有效的排序，當(dāng)然，稍微修改一下就可以支持負(fù)數(shù)的排序了。后面會給出我用Julia語言實(shí)現(xiàn)的沒有經(jīng)過優(yōu)化的代碼和一些測試結(jié)果。如果您對此能有什么改進(jìn)或者能幫嗎優(yōu)化一下代碼，請告知我一下，我會非常感謝您。下面是此算法的思想和原理。

2是一個神奇的數(shù)字，可以用來做很多東西，二叉樹，二分搜索，快速冪算法以及很多分治算法都是在2這個神奇的數(shù)字的幫助才能達(dá)到他們的優(yōu)雅和高效率。

利用二進(jìn)制，我們也可以進(jìn)行快速排序。

如果要對一列數(shù)字進(jìn)行排序，你會怎樣去做呢？學(xué)過快速排序的同學(xué)應(yīng)該會立即想到快速排序。先選一個數(shù)字，然后從兩邊開始，分別把小于它的數(shù)字交換到它的左邊，把大于它的數(shù)字交換到它右邊，完成這一過程，其右邊的數(shù)字全體大于等于它，左邊的數(shù)字全部小于等于它。然后分別對其左邊和右邊遞歸地運(yùn)用此方法（快速排序）進(jìn)行排序，當(dāng)排序的長度小于2時，遞歸過程完成了，這一列數(shù)字也就變成有序的了。

這種最基本的快排算法是不是也散發(fā)著二分的思想？如果它再二一點(diǎn)會怎樣？那就是我下面想要談?wù)摰幕诙M(jìn)制的快速排序算法了。哈哈，我給它加入了二進(jìn)制。

其實(shí)除開二進(jìn)制的位運(yùn)算，這個算法跟快速排序算法基本上是一樣的，所以我暫且稱之為BQuickSort（Binary or Bit）。

算法的基本思想

對每一個二進(jìn)制位，把該位是1的數(shù)字劃分到右邊，是0的劃分到左邊。高位優(yōu)先，通過交換來進(jìn)行。

實(shí)現(xiàn)

在算法的實(shí)現(xiàn)上我采用了按位與運(yùn)算，先用

的時間復(fù)雜度求出其中最大的數(shù)字，然后對最大的數(shù)字進(jìn)行一次簡單的flp2運(yùn)算（把其二進(jìn)制最高位之外的bit全部置0，這里的最高位并非64或32等，而是左邊第一個不為0的bit），獲得一個為2的n次冪的整數(shù)變量，我們暫且把它命名為shift。

每一次所做的就是用這個shift與一個要排序的區(qū)間段進(jìn)行按位與運(yùn)算運(yùn)算，將右邊運(yùn)算結(jié)果為0的數(shù)字同左邊運(yùn)算結(jié)果不為0的數(shù)字進(jìn)行交換，并返回交換之后的分割位置。然后遞歸地將同樣的算法運(yùn)用于分割位置的左邊和右邊，只需將shift右移一位即可。遞歸結(jié)束的條件是區(qū)間寬度小于1或者shift等于0。

對于一次部分排序，我寫了兩個函數(shù)，一個像快速排序那樣從兩邊向中間行進(jìn)，是不穩(wěn)定的算法，另一個只從左邊行進(jìn)，應(yīng)該是穩(wěn)定的算法。

---

演示

接下來我將演示對下列所示的整數(shù)序列進(jìn)行的BQuickSort。

在這里最大的數(shù)字是10(二進(jìn)制為1010)，通過對10進(jìn)行flp2運(yùn)算，我們將獲得一個數(shù)字8（二進(jìn)制為1000）。

將shift（這里為8）同每一個數(shù)字進(jìn)行按位與運(yùn)算并把運(yùn)算結(jié)果不為0的數(shù)字交換到右邊，最后我們返回一個整數(shù)索引10，它記錄了一次排序之后的分割線（分割線左邊的數(shù)字都小于8，同8進(jìn)行按位與運(yùn)算為0；右邊的數(shù)字都大于等于8，同8進(jìn)行按位與運(yùn)算不為0）。

鑒于分割線及其右邊的數(shù)字都大于左邊的數(shù)字，下面值演示對左邊的數(shù)字進(jìn)行的排序，同樣的方法適用于右邊。

將shift右移一位（結(jié)果為4），然后與分割線左邊的數(shù)字（前9個）進(jìn)行與上面一樣的部分排序操作，我們將得到下面這張圖所示的序列。

再對前3個數(shù)字進(jìn)行shift為2的部分排序，1將被交換到左邊，此時前3個數(shù)已經(jīng)有序，但是遞歸其實(shí)尚未結(jié)束，下一次遞歸是shift為1的一次部分排序。繼續(xù)對第4~9個數(shù)字執(zhí)行同樣的部分排序，最后我們將會得到前九個數(shù)字的有序排列。之后再對第10~12個數(shù)字進(jìn)行同樣的部分排序，我們就會得到一個所有數(shù)字的有序排列。

---

更新：以前隨便寫的文章，用語有點(diǎn)輕佻。我以前以為利用被注釋了的那個bqpartition函數(shù)，寫出來的快速排序是穩(wěn)定的，現(xiàn)在我不這么認(rèn)為。我現(xiàn)在認(rèn)為它是不穩(wěn)定的，形式化證明應(yīng)該不難，用計(jì)算機(jī)也很好驗(yàn)證，用那個bqpartition來做基數(shù)排序，以0，1為基數(shù)，排序結(jié)果不正確，所以它是不穩(wěn)定的。其次，可以輕易舉出這么一個例子：對于這樣的序列[1, 1, 2]，一次bqpartition將會得到這樣的結(jié)果，[2, 1, 1]，兩個1的位置被交換了，所以它是不穩(wěn)定的。沒有被注釋的那個bqpartition要快一點(diǎn)，因?yàn)楸蛔⑨尩袅说哪莻€bqpartition對于一個數(shù)，可能要交換不止一次才能到達(dá)最后位置。（這篇文章的代碼，以前是用Julia語言實(shí)現(xiàn)的，沒有改變語義，僅僅改變語法，Julia實(shí)現(xiàn)的比C語言實(shí)現(xiàn)（未經(jīng)優(yōu)化）的略快一些，現(xiàn)在為了讀者方便，改用C語言實(shí)現(xiàn)的。除了這個引用塊里面的更新說明和代碼更改，其他一切保持原樣（縱有不足之處））。

算法實(shí)現(xiàn)代碼

BqSort排序算法的C語言實(shí)現(xiàn)

// bqsort.c

各種排序算法的測試代碼及測試結(jié)果(經(jīng)過gcc -O3編譯優(yōu)化)見

各種排序算法效率簡單比較?github.com

。可見，對于正整數(shù)的排序，BqSort的速度基本上算是最快的了，尤其是有大量重復(fù)數(shù)字的時候，雖然這時Quick3Way(三路快排)也很快。不過BqSort可以保證O(nlogn)的最壞情況，而三路快排很容易會陷入O(N^2)的時間復(fù)雜度，比如N個不同的數(shù)正序或逆序排列。

。

總結(jié)

以上是生活随笔為你收集整理的快速排序算法_基于位运算的快速排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。