C++ 原地归并

起因是之前面百度,被面试官鄙视在了原地归并,后来翻了翻代码,其实不难,可能是当时没有突破思维把。

刚刚hzh又提起原地归并,发现自己都忘的差不多了,坑爹,还是写下来。


void merge(int * v, int n, int pos) // 数组v, 有n个元素,从pos位置开始分割,前后两段分别有序
{
    int fir = 0, sec = pos;
    while (fir < sec && sec < size) {
    while (fir < sec && v[fir] <= v[sec]) fir ++;
    int max_move = 0;

    while (sec < size && v[fir] > v[sec]) sec++, max_move++; // 核心,用来统计这一段元素到底该插到什么地方。
    exchange(&v[fir], sec-fir, sec-fir -max_move) ; // 特殊的放置函数,后面会举个栗子的
    fir += max_move;
    }

}

例如:       1 2 6 7 | 4 5 9 8  n=8 pos = 4
首次循环停止时, fir =  2 , 因为 v[2] = 6 > v[4] = 4,  
随后 sec 和 max_move 加了两次,因为 v[2] = 6 < v[6] = 9

传入 exchange的参数为  (&v[2], 4, 2) 

表示从第三个位置开始(也就是6在的位置),之后的4个元素(包括它),整体循环右移2次,

然后就变成了 1 2 4 5 6 7 9 8,  fir + max_move, 移到它的新位置,后面的特例就不再分析了。

最后这个方法的复杂性就落在了 exchange上,不过如果用链表来实现就很低了,想来当时的面试官是想这样考我的。。

此条目发表在C, 编程分类目录,贴了, 标签。将固定链接加入收藏夹。

C++ 原地归并》有4条回应

  1. zehua说:

    很荣幸的被大牛点名了~~
    mark…

  2. felix021说:

    我就不信你这段代码能通过编译……

zehua进行回复 取消回复

邮箱地址不会被公开。 必填项已用*标注