V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zeroday
V2EX  ›  问与答

写了一个归并排序实在看不出来哪里逻辑有问题,还请指点一下

  •  
  •   zeroday · 2015-04-09 10:12:51 +08:00 · 2166 次点击
    这是一个创建于 3515 天前的主题,其中的信息可能已经有所发展或是发生改变。
    #include <stdio.h>
    #include <stdlib.h>
    typedef int T;
    
    
    void merge(T _elem[], int lo, int mi, int hi)
    {
        // lb, lc 作为待排序数组左右两块的边界哨兵
        int lb = mi - lo, lc = hi - mi;
    
        // 开辟一个临时的空间用于存储前半段待排序数组
        T* B = (T* )malloc(sizeof(T)*lb);
        // 将前半段待排序数组复制到临时空间 B 中
        for (int i = 0; i < lb; i++) B[i] = _elem[i];
    
        // 待排序数组的后半段为 C
        T* C = _elem + mi;
    
        // B[j]和C[k]中的小者续至A末尾
        for (int i = 0, j = 0, k = 0; j < lb || k < lc;)
        {
            if (j < lb && (lc <= k || B[j] <= C[k])) _elem[i++] = B[j++];
            if (k < lc && (lb <= j || C[k] < B[j])) _elem[i++] = C[k++];
        }
        free(B);
    }
    
    void mergeSort(T _elem[], int lo, int hi)
    {
        if (hi - lo < 2) return;
        int mi = (lo + hi) >> 1;
        mergeSort(_elem, lo, mi);
        mergeSort(_elem, mi, hi);
        merge(_elem, lo, mi, hi);
    }
    
    int main()
    {
        T elem[19] = {53, 130, 120, 14, 206, 31, 380, 39, 402, 146, 491, 51, 54, 59, 722, 79, 82, 186, 92};
        mergeSort(elem, 0, 19);
        for (int i = 0; i < 19; i++)
            printf("%d\t", elem[i]);
        return 0;
    }
    
    6 条回复    2015-04-09 21:32:41 +08:00
    diamrem
        1
    diamrem  
       2015-04-09 10:29:41 +08:00   ❤️ 1
    for (int i = 0; i < lb; i++) B[i] = _elem[i];

    每次都从_elme的第一个元素开始复制到临时数组里面?这里应该是_elem[lo +i]之类的吧

    后面没看。

    找个小input用gdb或者lldb之类的调调吧……
    SPACELAN
        2
    SPACELAN  
       2015-04-09 12:53:07 +08:00
    1. mergeSort(elem, 0, 19) >> mergeSort(elem, 0, 18), 第三个参数表示下标,不是长度。

    2. mergeSort(_elem, mi, hi) >> mergeSort(_elem, mi + 1, hi),子序列不要有重叠。
    zeroday
        3
    zeroday  
    OP
       2015-04-09 15:56:06 +08:00
    @diamrem _elme[] 似乎没有问题,传入的参数 lo = 0
    zeroday
        4
    zeroday  
    OP
       2015-04-09 15:58:50 +08:00
    @SPACELAN 好像不是这个问题,这里第三个参数,我作为哨兵,并且取不到这个下标。所以这个样看来

    mergeSort(elem, 0, 19)
    mergeSort(_elem, mi, hi) 就没错了。
    因为在 mergeSort(_elem, lo, mi) 中本来就取不到 mi.
    arbipher
        5
    arbipher  
       2015-04-09 16:10:30 +08:00   ❤️ 1
    稍微看了一下

    首先把main函数改成:
    https://gist.github.com/arbipher/181c8456b04498e9c951

    跑一下,发现结果是
    1 2 2

    推测是merge出了问题

    然后把
    merge(_elem, lo, mi, hi);
    注释掉,再跑一下

    结果是
    1 3 2

    证明merge肯定有错
    也就是说你的代码把merge之前的1 3 2
    marge成了1 2 2

    merge函数我没有仔细看,但是你最后的for循环用的是有问题的,你在循环体内修改了循环参数
    (很久不写C了不知道会有什么问题)
    建议你改成while循环
    zeroday
        6
    zeroday  
    OP
       2015-04-09 21:32:41 +08:00
    @diamrem
    @arbipher
    @SPACELAN 谢谢帮助。发现两个问题。

    填充临时变量 B 应该从 下标 lo + i 开始。
    merge 中 for 循环 i 初始化应该为 lo.

    for ( int i = lo, j = 0, k = 0; j < lb || k < lc;)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1320 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 17:38 · PVG 01:38 · LAX 09:38 · JFK 12:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.