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; 
} 

启动[]的输出，这是鳍[]是：

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]; 
    } 
} 

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