递归合并排序重复元素打印

Question

我在下面的代码中遇到问题... 此代码是递归合并排序，但打印的数组具有数组中的重复元素。帮我找出问题所在。

void merge(int arr[], int l, int mid, int h) {
    int i = l;
    int j = mid + 1;
    int k = l;
    int b[h + 1];
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            b[k++] = arr[i++];
        else
            b[k++] = arr[j++];
    }
    while (i <= mid)
        b[k++] = arr[i++];
    while (j <= h)
        b[k++] = arr[j++];
        
    for (int i = 0; i <= h; i++)
        arr[i] = b[i];
}

void Rmerge_sort(int arr[], int l, int h)
{
    if (l < h) {
        int mid = (h + l) / 2;
        Rmerge_sort(arr, l, mid);
        Rmerge_sort(arr, mid + 1, h);
        merge(arr, l, mid, h);
    }
}

int main() {
    int arr[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 10 }, n = 10;
    
    Rmerge_sort(arr, 0, n - 1);
   
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

Answer 1

您定义数组 b 的大小为 h + 1 而不是 h - l + 1。合并循环将元素复制到索引值 l 到 h，但最终复制循环采用从 0 到 h 的元素，从未初始化的部分复制元素。

这是更正后的版本：

void merge(int arr[], int l, int mid, int h) {
    int len = h - l + 1;
    int i = l;
    int j = mid + 1;
    int k = 0;
    int b[len];
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            b[k++] = arr[i++];
        else
            b[k++] = arr[j++];
    }
    while (i <= mid)
        b[k++] = arr[i++];
    while (j <= h)
        b[k++] = arr[j++];
        
    for (int i = 0; i < len; i++)
        arr[l + i] = b[i];
}

但是请注意，解决此问题的更好方法是仅保存要合并的切片的左半部分，并将 h 视为切片末尾后第一个元素的索引。这避免了混淆和容易出错的 +1/-1 调整并减少了副本数：

void merge(int arr[], int low, int mid, int hi) {
    int len1 = mid - lo;
    int b[len1];
    int i, j, k;

    for (i = 0; i < len1; i++)
        b[i] = a[low + i];

    for (i = 0, j = mid, k = lo; i < len;) {
        if (j >= hi || arr[i] <= arr[j])
            arr[k++] = b[i++];
        else
            arr[k++] = arr[j++];
    }
}

void Rmerge_sort(int arr[], int low, int hi) {
    if (hi - low > 1) {
        int mid = low + (hi - low) / 2;  // avoid arithmetic overflow
        Rmerge_sort(arr, low, mid);
        Rmerge_sort(arr, mid, hi);
        merge(arr, low, mid, hi);
    }
}

int main() {
    int arr[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    Rmerge_sort(arr, 0, n);
   
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

递归合并排序重复元素打印

recursive merge sort repetitive element print

recursion

mergesort