时间戳

首页 > 解决方案 > 使用归并排序对数组进行排序

c++ - 使用归并排序对数组进行排序

问题描述

我正在使用合并排序来降低我的数组。我的第一个元素改变了他的值的原因是什么？我的一半代码有效。但是我的第一个和最后一个元素出了点问题。

#include <iostream>

void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid + 1, k = 0;
    int temp[high - low + 1];

    while (i <= mid && j <= high) {
        if (a[i] > a[j])
            temp[k++] = a[i++];

        else
            temp[k++] = a[j++];
    }

    while (i <= mid) {
        temp[k++] = a[i++];
    }

    while (j <= high) {
        temp[k++] = a[j++];
    }
    for (i = low; i <= high; i++) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);

        Merge(a, low, high, mid);
    }

    return;
}

void output(int* a, int n)
{
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << "\t";
    }
}

int main()
{
    int n;
    std::cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    MergeSort(a, 0, n);
    output(a, n);
}

输出必须是这个。

输入 10

1 2 3 4 5 6 7 8 9 10

输出

10 9 8 7 6 5 4 3 2 1

但我得到这个输出

4197055 10  9   8   7   6   5   4   3   2

我是 C++ 的初学者。所以如果你能帮助我在这里完成我的第一步，我会很高兴。

标签： c++sortingmergeconditional-statementsoutput

解决方案

您混淆了索引范围的描述方式。在相同的情况下，您使这些范围在最后关闭，而在其他情况下在最后打开。结果是未定义的行为缓冲区溢出。

这是固定版本，其中low指向第一个元素并high指向最后一个元素之外的一步。

请记住，在 C++ 中，数组的索引arr[n]应该是 from0到n - 1inclusive。

void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid, k = 0;
    int temp[high - low];

    while (i < mid && j < high) {
        temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    }

    while (i < mid) {
        temp[k++] = a[i++];
    }

    while (j < high) {
        temp[k++] = a[j++];
    }

    for (i = low; i < high; i++) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low + 1 < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid, high);

        Merge(a, low, high, mid);
    }

    return;
}

https://godbolt.org/z/nET5YT

推荐阅读