1

我正在尝试实现合并排序算法。我从算法书中的伪代码开始。伪代码将数组中的第一个位置指示为 1 而不是 0。我很难尝试实现代码。

这就是我所拥有的。我尝试通过在每一步打印出结果来逐步执行递归，但此时它非常复杂。

#include <iostream>
#include <deque>
using size_type = std::deque<int>::size_type;
void print(std::deque<int> &v)
{
    for(const auto &ref:v)
        std::cout << ref << " ";
    std::cout << std::endl;
}
void merge(std::deque<int> &vec, size_type p, size_type q, size_type r)
{
    int n_1 = q - p;
    int n_2 = r - q;
    std::deque<int> left, right;
    for(auto i = 0; i != n_1; i++)
        left.push_back(vec[p + i]);
    for(auto j = 0; j != n_2; j++)
        right.push_back(vec[q + j]);
    int i = 0, j = 0;
    std::cout << "left = ";
    print(left);
    std::cout << "right = ";
    print(right);
    for(auto k = p; k != r; k++) {
        if((i != n_1 && j != n_2) && left[i] <= right[j]) {
            vec[k] = left[i];
            i++;
        }
        else if(j != n_2){
            vec[k] = right[j];
            j++;
        }
    }
}
void merge_sort(std::deque<int> &A, size_type p, size_type r)
{
    int q;
    if(p < r - 1) {
        q = (p + r)/2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}
int main()
{
    std::deque<int> small_vec = {1, 6, 2, 10, 5, 2, 12, 6};
    std::deque<int> samp_vec = {2, 9, 482, 72, 42, 3, 4, 9, 8, 73, 8, 0, 98, 72, 473, 72, 3, 4, 9, 7, 6, 5, 6953, 583};
    print(small_vec);
    merge_sort(small_vec, 0, small_vec.size());
    print(small_vec);
    return 0;
}

运行程序时，我得到以下输出：

left = 1 
right = 6 
left = 1 6 
right = 2 10 
left = 2 
right = 12 6 
left = 1 2 6 10 
right = 5 2 12 6 
1 2 5 2 6 10 12 6
4

2 回答 2

1

错误在这里：(i != n_1 && j != n_2) && left[i] <= right[j])当i != n_1评估为 false时vec[k] = right[j];执行 - 正确。

但是如果i != n_1计算结果为true假j != n_2，即j = n_2您的程序尝试vec[k] = right[j];再次执行此操作，即访问您的双端队列的边界。

按如下方式重写你的 for 循环： if (i<n_1 && (j>=n_2 || left[i] <= right[j]) 此循环仅由于 C++ 的条件短路而起作用，即当j>=n_2评估为时true，left[i] <= right[j]永远不会再次检查，并且您不会越界访问双端队列。

left[i] <= right[j]i<n_1只有当两者都为真和假时才被检查，j>=n_2否则执行第二个分支。

于 2013-09-14T21:34:02.287 回答
1

在花费了大量时间并在另一篇文章中获得了一些有价值的帮助之后，才能够让算法正确运行。

正确代码：

#include <iostream>
#include <deque>
using size_type = std::deque<int>::size_type;
void print(std::deque<int> &v)
{
    for(const auto &ref:v)
        std::cout << ref << " ";
    std::cout << std::endl;
}
void print(int arr[], int size)
{
    for(int i = 0; i != size; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}
void merge(std::deque<int> &vec, size_type p, size_type q, size_type r)
{
    int n_1 = q - p + 1;
    int n_2 = r - q;
    std::deque<int> left, right;
    int i = 0, j = 0;
    while(i < n_1)
        left.push_back(vec[p + i++]);
    while(j < n_2)
        right.push_back(vec[j++ + q + 1]);
    i = 0; j = 0;
    //std::cout << "left = ";
    //print(left);
    //std::cout << "right = ";
    //print(right);
    for(auto k = p; k <= r; k++) {
        if((i < n_1 && left[i] <= right[j]) || j >= n_2) {
            vec[k] = left[i++];
        }
        else if(j < n_2){
            vec[k] = right[j++];
        }
    }
}
void merge_sort(std::deque<int> &A, size_type p, size_type r)
{
    int q;
    if(p < r) {
        q = (r + p) / 2;
        std::cout << "q = " << q << std::endl;
        //std::cout << "p = " << p << std::endl;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}
int main()
{
    std::deque<int> small_vec = {10, 3, 6, 4, 1, 5, 3, 9, 7, 2, 8};
    std::deque<int> samp_vec = {2, 9, 482, 42, 3, 4, 9, 8, 73, 8, 0, 98, 72, 473, 72, 3, 4, 9, 7, 6, 5, 6953, 583};
    print(samp_vec);
    merge_sort(samp_vec, 0, samp_vec.size() - 1);
    print(samp_vec);
    return 0;
}
于 2013-09-15T14:43:48.693 回答