V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
SlientHunter
V2EX  ›  程序员

归并排序算法问题 c 语言实现

  •  
  •   SlientHunter · 2014-11-17 19:24:49 +08:00 · 2818 次点击
    这是一个创建于 3640 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我在网上查了一下归并排序算法,都需要分配一个新的数组,下面是我考虑的代码(不分配新的数组),不知道这样是否可行,效率如何,希望得到指点。

    void mergsort(int v[], int left, int right){
    int i, j, k, middle, temp;

    if((right-left) < 2){
    if(v[left] > v[right]){
    temp = v[left];
    v[left] = v[right];
    v[right] = temp;
    }
    return;
    }
    middle = (left + right) / 2;
    mergsort(v, left, middle);
    mergsort(v, middle+1, right);
    for(i=left, j=middle+1;j<=right;j++){
    if(v[i] >= v[j]){
    temp =v[j];
    k = j;
    while(k > i){
    v[k] = v[k-1];
    k--;
    }
    v[k]= temp;
    i++;
    }
    }
    }
    8 条回复    2014-11-18 13:21:25 +08:00
    Jaylee
        1
    Jaylee  
       2014-11-17 19:32:20 +08:00
    逼格不够高
    SlientHunter
        2
    SlientHunter  
    OP
       2014-11-17 19:34:08 +08:00
    @Jaylee 不懂啥意思
    nolouch
        3
    nolouch  
       2014-11-17 20:39:58 +08:00 via Android
    你合并那段,本来O(N)解决的,你又来了次O(N*N)的插入排序,,,还不去直接插入排序了呢。
    @SlientHunter
    jiang42
        4
    jiang42  
       2014-11-17 20:41:24 +08:00
    有错误吧-。-
    mergesort([1], 0, 0)应该会出bug
    jiang42
        5
    jiang42  
       2014-11-17 20:45:25 +08:00
    看错了,没问题
    heliumhgy
        6
    heliumhgy  
       2014-11-18 01:26:49 +08:00 via Android
    并归排序本来就不是in place的
    msg7086
        7
    msg7086  
       2014-11-18 08:10:22 +08:00
    不肯给空间,就多花时间。
    xylophone21
        8
    xylophone21  
       2014-11-18 13:21:25 +08:00
    这个接口定义看的很是醉人啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5597 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 06:43 · PVG 14:43 · LAX 22:43 · JFK 01:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.