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语言排序算法案例分析”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。