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

希望這有助於理解算法更好！