2-4算法复杂度：讲义上的非递归归并排序算法好像有误

来源：2-4 亲自试验自己算法的时间复杂度

JeffreyW_

2017-07-24

void __merge(int arr[], int l, int mid, int r, int aux[]){
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){

            if( i > mid )   { arr[k] = aux[j]; j ++;}
            else if( j > r ){ arr[k] = aux[i]; i ++;}
            else if( aux[i] < aux[j] ){ arr[k] = aux[i]; i ++;}
            else                      { arr[k] = aux[j]; j ++;}
        }
    }

    void mergeSort( int arr[], int n ){

        int *aux = new int[n];
        for( int i = 0 ; i < n ; i ++ )
            aux[i] = arr[i];

        for( int sz = 1; sz < n ; sz += sz )
            for( int i = 0 ; i < n ; i += sz+sz )
                __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1), aux );

        delete[] aux;

        return;
    }

这个排序算法的结果好像有误，请老师测试一下，谢谢！

我测试的结果:

随机生成数组: 4, 10, 9, 3, 8, 1, 7, 9, 9, 7

排序后的数组: 4, 9, 7, 10, 9, 3, 8, 1, 7, 9

写回答

1回答

liuyubobobo

2017-07-24

已采纳

非常抱歉，你说的对，这个代码确实有问题。在__merge中应该同步一下，让aux数组中[l,r]区域的元素等同于当前arr数组[l,r]区域的元素，才可以进一步使用aux数组进行归并操作。正确的代码如下：

void __merge(int arr[], int l, int mid, int r, int aux[]){    

    for(int i = l ; i <= r ; i ++)    
        aux[i] = arr[i];    

    int i = l, j = mid+1;    
    for( int k = l ; k <= r; k ++ ){    
        if( i > mid )   { arr[k] = aux[j]; j ++;}    
        else if( j > r ){ arr[k] = aux[i]; i ++;}    
        else if( aux[i] < aux[j] ){ arr[k] = aux[i]; i ++;}    
        else                      { arr[k] = aux[j]; j ++;}    
    }    
}  
  
void mergeSort( int arr[], int n ){    
  
    int *aux = new int[n];    
    for( int i = 0 ; i < n ; i ++ )    
        aux[i] = arr[i];    

    for( int sz = 1; sz < n ; sz += sz )    
        for( int i = 0 ; i < n ; i += sz+sz )    
            __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1), aux );    

    delete[] aux;    
    return;    
}

同时，课程的github代码也进行了修改，地址如下：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/02-Time-Complexity/Course%20Code%20(C%2B%2B)/04-Time-Complexity-Experiments/MyAlgorithmTester.h

非常感谢你指出的错误。如果愿意，可以加我的微信：liuyubobobo，我可以发给你一个小红包：）

JeffreyW_

谢谢波波老师！

2017-07-25

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

查看课程

相似问题

lc203 递归写法复杂度分析