c語言排序算法案例分析

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

在歸并算法中，合并兩個數(shù)列需要消耗m+n的空間，排序好了后還要將隊列拷回。在我的版本的算法中，可一開始就申請一塊等長內(nèi)存，然后順次的寫入數(shù)據(jù)，而不需要寫回，一遍寫完后，交換兩塊內(nèi)存，繼續(xù)寫。這樣減少了一半的寫開銷，避免了重復申請空間的問題。

交換次數(shù)決定了排序完成時正確的數(shù)據(jù)寫入到了哪塊內(nèi)存中。

當交換次數(shù)為偶數(shù)時，寫入原內(nèi)存。

當交換次數(shù)為奇數(shù)時，寫入臨時內(nèi)存。

如果交換次數(shù)為奇數(shù)，那么還要將數(shù)據(jù)拷貝至原內(nèi)存。不過，在兩兩交換時，不需要額外的內(nèi)存，因為比較數(shù)據(jù)只有一個，簡單交換就行了，奇數(shù)次時先進行一次比較，接下來就仍然是偶數(shù)次的了。因此在算法的主要部分前面才有了這段代碼。

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); }

這段代碼雖然完成了任務，但是有處地方特么讓人不爽。就是在算交換次數(shù)的地方，用了一個O(n)的循環(huán)來獲得次數(shù)。感覺有點不效率。

事實上我們只在乎長度數(shù)量的***1位在哪，因為那一位才決定交換次數(shù)。

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

比如 

x&(x-1) 

可將X最右邊起的連續(xù)的0填充為1

x&(-x)

可單獨抽出最右邊的1

等等。

所以總是覺得，咱們的問題，也是能用O(1)解決的。

但是這些簡單好用的魔法似乎都只和數(shù)的右側(cè)沾邊，因為操縱右邊的位數(shù)，可以用確切知道的數(shù)，比如1  或FFFFFF，而想像操作右邊位一樣操作左邊位就不行了，除非你知道該數(shù)的log base 2  interger是什么……如果我們有辦法填充最左邊的0，就能得解，但這個看似很簡單的問題，居然是個至今都無解的題，除非新版cpu出了求專門問題對應的指令，要想在低于logN的步驟內(nèi)解決這個似乎不可能了。

不過對我們的應用來說，這還沒到頭，因為最終的目的是要知道該位是在奇數(shù)位上還是在偶數(shù)位上。因此問題轉(zhuǎn)換為：

把數(shù)組長度-1，如果最左邊的1落在偶數(shù)位上，則需要偶數(shù)次交換，如果落在奇數(shù)位上則需要奇數(shù)次交換

這樣一來問題似乎很好解決了，這是改寫后的代碼

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

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