C++合并排序问题

Question

我是 c++ 新手，正在尝试开发合并排序代码。我用大小为 15 的样本数组对其进行了测试，但代码给出的答案是不正确的。我不知道出了什么问题。这是我的代码：

#include <stdlib.h>
#include <stdio.h> 
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <unistd.h>
#include <cstdlib>

using namespace std;

//two arrays, input
int initial[15] = {200,1,2,9,8,98,6,44,5,4,67,15,3,2,0};
//for output
int fin[15];

void sort(int* ini, int left, int right, int m);

//saperate the input in a recursion
void devide(int* ini, int left, int right){
     int m;

     if(left < right){
          m = (left + right) / 2;
          devide(ini, left, m);
          devide(ini, m+1, right);

          sort(ini, left, right, m);
     }
}


//sorting
void sort(int* ini, int left, int right, int m){

     //first half, start at the first element in the input array
     int first_h = left;

     //second half, start at the first element after the 
     // middle element in the input array
     int second_h = m+1;

     //index for output array
     int out = left;

     //comparing, if both half of array have element
     while(first_h <= m && second_h <= right){

          //put the smaller in the the output array
          if(initial[first_h] < initial[second_h]){
               fin[out] = initial[first_h];
              first_h++;
          }
          else{
               fin[out] = initial[second_h];
               second_h++;

          }  
          out++;   
     }

     //if one of half of input is empty, put the rest element into the 
     // output array
     while(first_h <= m){
          fin[out] = initial[first_h];
          out++;
      first_h++;
     }
     while(second_h <= right){
          fin[out] = initial[second_h];
          out++;
          second_h++;
     }
}

int main(){
     devide(initial, 0, 14);

     for(int i =0; i<15; i++){
          cout<<fin[i];
          cout<<",";
     }
     return 0;
}

initiation[] 的输出，即 fin[] 是：

5,4,67,15,3,2,0,200,1,2,9,8,98,6,44,

Answer 1

所以你没有考虑到的一个小错误是，你正在传递指针数组 ini 但在方法内部你仍然使用方法 initial 还有一件事是，你应该接受一个临时数组会将排序后的值分配给您的 ini 数组。

因此您的代码应如下所示

  void sort(int* ini, int left, int right, int m){
     int first_h = left;
     int second_h = m+1;
     int out = left;
     while(first_h <= m && second_h <= right){
          if(ini[first_h] < ini[second_h]){
               fin[out] = ini[first_h];
              first_h++;
          }
          else{
               fin[out] = ini[second_h];
               second_h++;

          }  
          out++;   
     }

     while(first_h <= m){
          fin[out] = ini[first_h];
          out++;
      first_h++;
     }
     while(second_h <= right){
          fin[out] = ini[second_h];
          out++;
          second_h++;
     }
     for(int i=left; i<out; i++)
     {
       ini[i] = fin[i];
     }
}

希望这有助于更好地理解算法！

C++合并排序问题

c++ merge sort trouble

c++

mergesort