合并排序输出不正确

Question

所以，我已经遇到了一些问题，但我认为我自己已经取得了重大进展并且尝试了很多事情。但是我无法让它输出正确的值我在概念上理解合并排序，但编码它让我感到困惑。所以...如果我输入：

5 1个 7 4个 6个 9

而不是：14569，我得到了（我不明白为什么）： 11414761467 ** 另外，作为一个侧面的问题，是否有一种简单的方法可以循环输入一组数字，以便在这种情况下不需要在中间换行？

#include <iostream>
using namespace std;

void merge(int[], int, int, int);

void mergesort(int array[], int low, int high)
{
    int mid;
    if(low < high){
        mid = low + (high-low)/2;
        mergesort(array, low, mid);
        mergesort(array, mid+1, high);
        merge(array, low, mid, high);
    }
}

void merge(int array[], int low, int mid, int high)
{
    int h, i, j, b[high], k;
    h = low;
    i = low;
    j = mid + 1;
    while((h <= mid) && (j <= high)){
        if(array[h] <= array[j]){
            b[i] = array[h];
            h++;
        }
        else{
            b[i] = array[j];
            j++;
        }
        i++;
    }
    if( h > mid){
        for(k = j; k <= high; k++){
            b[i] = array[k];
            i++;
        }
    }
    else{
        for(k = h; k <= mid; k++){
            b[i] = array[k];
            i++;
        }
    }
    for( k = low; k <= high; k++){
        array[k] = b[k];
    }
    for(int i = 0; i < high; i++){
        cout << array[i];
    } 
}

int main()
{
    int size;
    cin >> size;
    int data[size];
    for(int i = 0; i < size; i++){
        cin >> data[i] ;
    }
    mergesort(data, 0, size-1);
}

还有没有一种方法可以 cin >> data[i] 而不必在每个数据后按 enter 键，但不使用向量？再次感谢。

Answer 1

你在 merge() 的每次递归中打印，这就是为什么你会这样，因为打印发生在合并发生时，而不仅仅是打印最终结果。

for(int i = 0; i < high; i++){
    cout << array[i];
}

为避免这种情况，在 main 中打印合并后的数组。

我的意思是将您的程序更改为：

#include <iostream>
using namespace std;

void merge(int[], int, int, int);

void mergesort(int array[], int low, int high)
{
    int mid;
    if(low < high){
        mid = (high+low)/2;
        mergesort(array, low, mid);
        mergesort(array, mid+1, high);
        merge(array, low, mid, high);
    }
}

void merge(int array[], int low, int mid, int high)
{
    int h, i, j, b[high], k;
    h = low;
    i = low;
    j = mid + 1;
    while((h <= mid) && (j <= high)){
        if(array[h] <= array[j]){
            b[i] = array[h];
            h++;
        }
        else{
            b[i] = array[j];
            j++;
        }
        i++;
    }
    if( h > mid){
        for(k = j; k <= high; k++){
            b[i] = array[k];
            i++;
        }
    }
    else{
        for(k = h; k <= mid; k++){
            b[i] = array[k];
            i++;
        }
    }
    for( k = low; k <= high; k++){
        array[k] = b[k];
    }
}

int main()
{
    int size;
    cin >> size;
    int data[size];
    for(int i = 0; i < size; i++){
        cin >> data[i] ;
    }
    mergesort(data, 0, size-1);
    for(int i = 0; i < size; i++){
        cout << data[i];
    } 
}

合并排序输出不正确

Merge Sort Output isn't Correct

c++

mergesort