时间戳

首页 > 解决方案 > 合并排序：超过时间限制

c++14 - 合并排序：超过时间限制

问题描述

为什么我time limit exceeded在使用归并排序算法对数组进行排序时出错？我的代码有什么问题？我输入了 9 个元素。

输入：4 2 1 8 5 9 6 7 0

输出：Time limit exceeded

#include <bits/stdc++.h>

using namespace std;
int a[100];

void merge(int a[], int l, int r, int m) {
    int t[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i <= m)
        t[k++] = a[i++];
    while (j <= r)
        t[k++] = a[j++];
    for (int i = l; i <= r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r) {
    if (l > r)
        return;

    int m = (r + l) / 2;
    msort(a, l, m);
    msort(a, m + 1, r);
    merge(a, l, r, m);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

标签： c++14mergesort

解决方案

您的代码中存在一些问题：

  • 终止 in 的测试msort()不正确：当切片包含单个元素或更少元素时，您应该停止。您目前在 1 个元素的切片上永远循环。

    if (l >= r) return;

  • 您应该测试从用户读取的元素main()数量n是否不大于您读取要排序的元素100的全局数组的大小。a您应该改用具有适当大小的本地数组或从堆中分配数组。tin的临时数组merge()也可能太大而无法自动分配。一次分配临时空间并递归传递它更有效。

另请注意，在 C 和 C++ 中，使用第一个元素的索引和最后一个元素之后的元素的索引来指定数组切片是惯用的。这简化了代码并允许空数组并避免无符号索引类型的特殊情况。

这是使用这种方法的修改版本：

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int l, int r, int m, int t[]) {
    int i = l, j = m, k = 0;
    while (i < m && j < r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i < m)
        t[k++] = a[i++];
    while (j < r)
        t[k++] = a[j++];
    for (int i = l; i < r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r, int t[]) {
    if (r - l > 1) {
        int m = l + (r - l) / 2;
        msort(a, l, m, t);
        msort(a, m, r, t);
        merge(a, l, r, m, t);
    }
}

void msort(int a[], int n) {
    if (n > 1) {
        int *t = new int[n];
        msort(a, 0, n, t);
        delete[] t;
    }
}

int main() {
    int n;

    cin >> n;
    if (n <= 0)
        return 1;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete[] a;
    return 0;
}

推荐阅读