從發明新的排序算法開始扯淡
像這樣簡單的算法前人工程師肯定想到過，即使你是初學者，如果偶然發現了這個也并不稀罕，我也沒有打算效仿郭小四竊他人成果自居，說到底這只是一篇系列扯淡文，它真正有價值的部分是由此延伸出來的問題。
在歸并算法中，合并兩個數列需要消耗m+n的空間，排序好了后還要將隊列拷回。在我的版本的算法中，可一開始就申請一塊等長內存，然后順次的寫入數據，而不需要寫回，一遍寫完后，交換兩塊內存，繼續寫。這樣減少了一半的寫開銷，避免了重復申請空間的問題。
交換次數決定了排序完成時正確的數據寫入到了哪塊內存中。
當交換次數為偶數時，寫入原內存。
當交換次數為奇數時，寫入臨時內存。
如果交換次數為奇數，那么還要將數據拷貝至原內存。不過，在兩兩交換時，不需要額外的內存，因為比較數據只有一個，簡單交換就行了，奇數次時先進行一次比較，接下來就仍然是偶數次的了。因此在算法的主要部分前面才有了這段代碼。
- int temp = len,i = 0,size = 1;
- int l1p,l1end,l2p,l2end;
- int *templist,*listb;
- printarr(list,len);
- if(len<=1){
- return;
- }
- i = 0;
- //calculate swaptimes
- while(temp){
- temp = temp>>1;
- i++;
- }
- if(i%2){
- for(i=0;(i+1)<len;i+=2){
- if(list[i]>list[i+1]){
- temp = list[i];
- list[i] = list[i+1];
- list[i+1] = temp;
- }
- }
- size = 2;
- printarr(list,len);
- }
這段代碼雖然完成了任務，但是有處地方特么讓人不爽。就是在算交換次數的地方，用了一個O(n)的循環來獲得次數。感覺有點不效率。
事實上我們只在乎長度數量的***1位在哪，因為那一位才決定交換次數。
于是開始尋找有沒有更快的方法。在英文中這個問題叫Find the log base 2 of an integer，這里有一個斯坦福的頁面講這個問題 http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
很遺憾的是，關于此問題，目前最快解也只有logN，基于二分查找法。但是把N降為logN，對于數位長度來說，真有點小題大做，仍然還是想找一個O(1)的方法才有意義。
之所以有這種想法，因為在位操作的世界里，有些算法很是銷魂。
比如
x&(x-1)
可將X最右邊起的連續的0填充為1
x&(-x)
可單獨抽出最右邊的1
等等。
所以總是覺得，咱們的問題，也是能用O(1)解決的。
但是這些簡單好用的魔法似乎都只和數的右側沾邊，因為操縱右邊的位數，可以用確切知道的數，比如1 或FFFFFF，而想像操作右邊位一樣操作左邊位就不行了，除非你知道該數的log base 2 interger是什么……如果我們有辦法填充最左邊的0，就能得解，但這個看似很簡單的問題，居然是個至今都無解的題，除非新版cpu出了求專門問題對應的指令，要想在低于logN的步驟內解決這個似乎不可能了。
不過對我們的應用來說，這還沒到頭，因為最終的目的是要知道該位是在奇數位上還是在偶數位上。因此問題轉換為：
把數組長度-1，如果最左邊的1落在偶數位上，則需要偶數次交換，如果落在奇數位上則需要奇數次交換
這樣一來問題似乎很好解決了，這是改寫后的代碼
- int temp = len-1,i = 0,size = 1;
- int l1p,l1end,l2p,l2end;
- int *templist,*listb;
- printarr(list,len);
- if(len<=1){
- return;
- }
- //calculate swaptimes,only if highest bit in odd place
- if((temp&0xaaaaaaaa)<(temp&0x55555555)){
- for(i=0;(i+1)<len;i+=2){
- if(list[i]>list[i+1]){
- temp = list[i];
- list[i] = list[i+1];
- list[i+1] = temp;
- }
- }
- size = 2;
- printarr(list,len); }
0xAAA...AA可以稱為偶數柵，0x555...55可以稱為奇數柵，如果***位在偶數位上，偶數 柵相與的結果肯定大于和奇數 柵相與的結果的，反之亦是同理，此問題得解。
