Mergesort算法实现 [英] Mergesort algorithm implementation

问题描述

我已经完成了合并排序算法.我理解逻辑，但是我不明白为什么我们必须再次将b[]数组复制到a[]数组中.我们在b[]数组中输入的内容仅是排序后的数字，对吗?但是，如果我们打印b[]数组，我们将得到未排序的数组.一旦将其复制到a[]数组中，我们将获得正确的输出.谁能解释为什么我们必须将b[]数组复制到a[]数组?

I have gone through Merge sort algorithm. I understood the logic, but I didn't get why we have to copy the b[] array again into the a[] array. What we have entered in the b[] array are sorted numbers only, right? But, if we print the b[] array, we are getting unsorted array. Once we copy it into the a[] array, we are getting the correct output. Can anyone explain why we have to copy the b[] array to the a[] array?

算法::

void MergeSort(int low, int high) {
    if (low < high) { 
        int mid = (low + high) / 2;
        MergeSort(low, mid);
        MergeSort(mid + 1, high);
        Merge(low, mid, high);
    }
}

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

我实施的程序:

import java.util.Arrays;

public class Msort {
    public static void msort(int[] arr, int l, int h) {
        int m;
        if (l < h) {
            m = (l + h) / 2;
            msort(arr, l, m);
            msort(arr, m + 1, h);
            merge(arr, l, m, h);
        }
    }

    public static void merge(int arr[], int l, int m, int h) {
        int i = l, j = m + 1, k = l, n;
        int[] sarr = new int[arr.length];
        while ((i <= m) && (j <= h)) {
            if (arr[i] <= arr[j]) {
                sarr[k] = arr[i];
                i++;
            } else {
                sarr[k] = arr[j];
                j++;
            }
            k++;
        }
        if (i <= m) {
            for (n = i; n <= m; n++) {
                sarr[k] = arr[n];
                k++;
            }
        } else {
            for (n = j; n <= h; n++) {
                sarr[k] = arr[n];
                k++;
            }
        }

        for (k = l; k <= h; k++) {
            arr[k] = sarr[k];
        }
        System.out.println("arr" + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6, 7 };

        Msort.msort(arr, 0, arr.length - 1);
    }
}

推荐答案

合并排序的工作方式是将未排序的数据分解为单个元素，单个元素被视为已排序，然后将它们合并为更大的排序后的大块.

Merge sort works by splitting the unsorted data down into individual elements, a single element being considered sorted, and merging them back together in progrssively larger sorted chunks.

b数组是实现中的工作台"，并且在每次迭代(示例中为递归)结束时，保存该迭代的工作结果.通过将未排序的数组的左侧和右侧复制到b数组中来执行拆分.

The b array is the 'work bench' in your implementation and, at the end of each iteration (recursion in your example), holds the result of the work done that iteration. The split is peformed by copying the left and right sides of the unsorted array into the b array.

为了在拆分数组后备份"时构建合并结果，需要从组件重建结果，方法是将排序后的块复制回未排序的原始块.

In order to build the merged result as you come 'back up' from splitting the array, you need to rebuild the result from the components, which is done by copying the sorted chunk back over it's unsorted original.

如果更改了递归，则合并的方向(从左到右或从右到左/从低到高或从高到低)与递归的级别相对应，可以避免复制.没有b数组的完全原位复制合并排序是一个更复杂的算法.

The copy can be avoided if the recursion is changed so that the direction of the merge (left to right or right to left / low to high or high to low) corresponds with the level of the recursion. Full copy-in-place merge sort, without the b array, is a more complicated alogrithm.

这篇关于Mergesort算法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！