c++ - 合并排序 C++ 不排序

Question

我正在学习算法第一部分课程，我使用 C++ 实现了归并排序。它应该进行就地排序，但它不对数组进行排序。我无法找到原因。希望能得到积极的回应。谢谢你。

void merge(int *a, int *aux, int low, int mid, int high) {
    for (int k = low; k <= high; ++k)
        aux[k] = a[k]; // copy
    int i = low, j = mid + 1;
    for (int k = low; k <= high; ++k) { // merge
        if (i > mid)
            a[k] = aux[j++];
        else if (j > mid)
            a[k] = aux[i++];
        else if (aux[i] > aux[j])
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

void sort(int *a, int *aux, int low, int high) {
    if (high <= low)
        return;
    int mid = low + (high - low) / 2;
    sort(a, aux, low, mid);
    sort(a, aux, mid + 1, high);
    merge(a, aux, low, mid, high);
}

void sort(int *a, int N) {
    int *aux = new int[N];
    sort(a, aux, 0, N - 1);
}

标签： c++mergesort

Answer 1

您的合并功能在逻辑上不正确。对于任何迭代，最后两个条件将永远不会被执行。j将始终大于mid，控制不会超出第二个表达式。

将合并函数的定义修改为如下所示：

void merge(int *a, int *aux, int low, int mid, int high) {
    for (int k = low; k <= high; ++k)
        aux[k] = a[k]; // copy
    int i = low, j = mid + 1;
    for (int k = low; k <= high; ++k) { // merge

// changes begin here

        if (i <= mid and j <= high) {
            if (aux[i] > aux[j])
                a[k] = aux[j++];
            else
                a[k] = aux[i++];
        }
        else if (i > mid)
            a[k] = aux[j++];
        else // if (j > high)
            a[k] = aux[i++];

// changes end here

    }
}