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 && 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) {
        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 = 
right = 1 
left = 1 
right = 6 
left = 
right = 10 
left = 1 6 
right = 2 10 
left = 
right = 2 
left = 
right = 6 
left = 2 
right = 12 6 
left = 1 2 6 10 
right = 5 2 12 6 
1 2 5 2 6 10 12 6
4

1 回答 1

1

您的排序存在一些问题。首先，合并步骤是错误的。其次，您如何称呼合并是错误的。我会建议一些步骤来改进实施以得到正确的解决方案，也许它会帮助你。

首先我的合并代码：

void merge(std::deque<int> &vec, size_type p, size_type q, size_type r)
{
  std::deque<int> left, right;
  int i = p, j = q+1;
  while(i <= q) //change 1: to a while loop. expresses it a little simpler but 
                //you weren't inserting the correct left elements here
    left.push_back(vec[i++]);
  while(j <= r) //change 2: same thing, lets get the correct right values
    right.push_back(vec[j++]);
  i = 0; j = 0;
  for(auto k = p; k <= r; k++) {
    //change 3: alter this case to include the left over left elements! this is the main error
    if(i < left.size() && left[i] <= right[j] || j >= right.size())
        vec[k] = left[i++];
    else if(j < right.size())
        vec[k] = right[j++];
  }
}

然后将您调用 merge_sort 的方式更改为：

merge_sort(small_vec, 0, small_vec.size()-1); //change 4: initialized r wrong

这使排序对我有用。作为对我发现的问题的回顾：1）没有抓住正确的左右子数组。2) 没有正确处理合并 - 在右边消失后忘记抓取所有左边的元素。3）没有正确调用merg_sort，初始化r参数不正确。

于 2013-09-15T00:18:51.443 回答