随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

归并排序(merge sort)算法实现

    归并排序(merge sort)体现了分治的思想,即将一个待排序数组分为两部分,对这两个部分进行归并排序,排序后,再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)

实现代码如下:
#include <stdio.h> 
#include 
"common.h"  
void merge(int data[], int p, int q, int r) 
{     
    
int i, j, k, n1, n2;     
    n1 
= q - p + 1;     
    n2 
= r - q;     
    
int L[n1];     
    
int R[n2];      
    
for(i = 0, k = p; i < n1; i++, k++)         
        L[i] 
= data[k];     
    
for(i = 0, k = q + 1; i < n2; i++, k++)         
        R[i] 
= data[k];     
    
for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)     
    {         
        
if(L[i] > R[j])         
        {             
            data[k] 
= L[i];             
            i
++;         
        }         
        
else         
        {             
            data[k] 
= R[j];             
            j
++;         
        } 
    }
    
if(i < n1)     
    {         
        
for(j = i; j < n1; j++, k++)             
        data[k] 
= L[j];     
    }     
    
if(j < n2)     
    {         
        
for(i = j; i < n2; i++, k++)             
            data[k] 
= R[i];     
    }  
}
void merge_sort(int data[], int p, int r) 
{     
    
if(p < r)     
    {         
        
int q = (p + r) / 2;         
        merge_sort(data, p, q);         
        merge_sort(data, q 
+ 1, r);         
        merge(data, p, q, r);     
    } 


void test_merge_sort() 
{   
    
int data[] = {4412145-123-10121};     
    printf(
"-------------------------------merge sort----------------------------\n");    
    out_int_array(data, 
7);     
    merge_sort(data, 
06);     
    out_int_array(data, 
7); 


int main() 
{    
    test_merge_sort();    
    
return 0
}  




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-14 22:57 银河使者 阅读(3149) 评论(4)  编辑  收藏 所属分类: C/C++

评论

# re: 归并排序(merge sort)算法实现  回复  更多评论   

归并排序体现了分治的思想,很有价值
2008-05-16 12:19 | 网上买书

# re: 归并排序(merge sort)算法实现  回复  更多评论   

使用分治法实现基本正确。但是merge函数中有两个数组的定义:
int L[n1];
int R[n2];
在维数处使用了变量,不对。静态数组的维数必须在编译时确定,运行时动态给定数组维数需要使用动态内存分配。所以merge函数和mergesort函数都需要修改。

http://zhidao.baidu.com/question/75588993.html
2009-02-15 21:04 | 刚哥

# re: 归并排序(merge sort)算法实现  回复  更多评论   

@刚哥
这算法是很多年前写的,现在看看写成用变量定义数组了。估计是用Java用多了,不小心写成Java格式的了。以前这些算法好象都调试过,可能是这个没测试过。可能当初是写的示意代码。基本上都忘了细节了。^_^
2009-02-15 22:46 | 银河使者

# re: 归并排序(merge sort)算法实现  回复  更多评论   

@刚哥
你的那个是C++的算法,基本思路类型,都是数据结构讲的,哈哈!!这些数据结构书上都有,看看就知道了!
2009-02-15 22:47 | 银河使者

只有注册用户登录后才能发表评论。


网站导航: