c語言排序算法案例分析

本文小編為大家詳細介紹“c語言排序算法案例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“c語言排序算法案例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

在歸并算法中，合并兩個數列需要消耗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位在哪，因為那一位才決定交換次數。

之所以有這種想法，因為在位操作的世界里，有些算法很是銷魂。

比如 

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可以稱為奇數柵，如果***位在偶數位上，偶數  柵相與的結果肯定大于和奇數  柵相與的結果的，反之亦是同理，此問題得解。

讀到這里，這篇“c語言排序算法案例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。