使用c++的归并排序算法[已关闭]

Question

void merge(int *arr, int lo, int mid, int hi) {
    int* temp = new int[hi - lo + 1];
    int i = lo;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= hi)
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }
    while (j <= hi)
    {
        temp[k++] = arr[j++];
    }

    for(int a = 0; a < k; a++)
    {
        arr[lo + a] = temp[a];
    }
    
    delete[] temp;
}

3

1 2 3

当我输入 时，输出 0 1 2。为什么排序过程中要加0呢？我想要得到 1 2 3 个结果。

无论您输入什么，排序过程中都会添加零。

其他测试：

输入1： 4 1 2 4 5 输出1： 0 1 2 4 要求输出1： 1 2 4 5

Answer 1

根据 C++ 开发人员的经验，半开区间是 C++ 中描述范围的最佳方式。这意味着如果从 a 开始并在 b 结束，则范围内的元素为“a, a+1, a+2, ..., b-2, b-1”，并且不包括 b。

空范围表示为“a,a”对。像“mid”这样的东西很容易理解；范围是“开始，中间”和“中间，结束”。

在您的闭区间系统中，“中”的含义很难理解。第一个子间隔是“start, mid”还是“start, mid-1”？第二个音程是“mid, end”还是“mid+1, end”？在实践中，当您必须在端点上摆弄 +1 和 -1 时，您最终会遇到很多“栅栏”错误。

其次，手动内存管理（新建/删除）会造成泄漏。

其次，您的代码首先将所有内容合并到

temp

中，然后复制到

arr

中。由于代码应该做更少的事情，我们将把您的代码分为这两个步骤。

std::unique_ptr<int[]> merge( int const* lhs, int lhs_size, int const* rhs, rhs_size ) {
  auto retval = std::make_unique<int[]>( lhs_size+rhs_size ); // notice lack of +1

  int l_index = 0, r_index = 0;
  int out_index = 0;

  // The merge portion:
  while (l_index < lhs_size && r_index < rhs_size) {
    if (rhs[r_index] < lhs[l_index]) {
      retval[out_index++] = rhs[r_index++];
    } else {
      retval[out_index++] = lhs[l_index++];
    }
  }
  // copy the remainder
  if (l_index < lhs_size && out_index < (lhs_size+rhs_size)) {
    std::copy_n( lhs, (lhs_size-l_index), &retval[out_index] );
    out_index += (lhs_size-l_index);
  }

  if (r_index < rhs_size && out_index < (lhs_size+rhs_size)) {
    std::copy_n( rhs, (rhs_size-r_index), &retval[out_index] );
    out_index += (rhs_size-r_index);
  }

  return retval;
}

我们现在可以在此之上编写您的合并：

void merge(int *arr, int lo, int mid, int hi) {
{
  auto temp = merge( arr+lo, mid-lo, arr+mid, hi-mid );

  std::copy_n( &temp[0], hi-lo, &arr[lo+a] );
}

目标是以减少犯错误机会的方式编写代码。