合并排序无法正常工作。数组中的数字未排序

Question

以下是我在JAVA中进行合并排序的代码，但输出不是预期的。

给定的输入是 [49, 1, 3, 200, 2, 4, 70, 5]

输出为：

合并排序：[2, 4, 49, 1, 3, 70, 5, 200]

哪个号码没有排序。我相信问题出在合并方法中。有人可以帮忙吗？

merge_sort方法：

private static int[] merge_sort(int[] unsorted_array) {
        
        if (unsorted_array.length < 2) {
            return unsorted_array;
        }
        
        int mid = unsorted_array.length / 2;
        
        int[] first_array = new int[mid];
        int[] second_array = new int[unsorted_array.length - mid];
        
        //Copy element to first and second array.
        for (int i = 0; i < mid; i ++) {
            
            first_array[i] = unsorted_array[i];
        }
        
        for (int i = 0; i < second_array.length; i++) {
            
            second_array[i] = unsorted_array[mid + i];
        }
        
        merge_sort(first_array);
        merge_sort(second_array);
        
        int[] sorted_array = merge(first_array, second_array);
        
        return sorted_array;
    }

合并方法：

private static int[] merge(int[] first_array, int[] second_array) {
        int[] result = new int[first_array.length + second_array.length];
        
        int index_result = 0;
        int index_first = 0;
        int index_second = 0;
        
        while (index_first < first_array.length && index_second < second_array.length) {
            
            if (first_array[index_first] < second_array[index_second]) {
                
                result[index_result] = first_array[index_first];
                index_first++;      
            } else {
                
                result[index_result] = second_array[index_second];
                index_second++;
            }
            
            index_result++;
        }
        
        while (index_first < first_array.length) {
            
            result[index_result] = first_array[index_first];
            index_result++;
            index_first++;
        }
        
        while (index_second < second_array.length) {
            
            result[index_result] = second_array[index_second];
            index_result++;
            index_second++;
        }
        
        return result;
    }

Answer 1

您没有使用排序后的中间结果进行合并，而是使用原始拆分数组。修改您的代码如下：

first_array = merge_sort(first_array);
second_array = merge_sort(second_array);
        
int[] sorted_array = merge(first_array, second_array);

此外，您不需要创建这些中间数组。您只需将低指针、高指针传递给您的数组，以指示您正在排序和合并的数组部分。

喜欢：

private static void merge_sort(int[] unsorted_array, int low, int high) {
        
   if (low == high) return;
                    
   int mid = low + ( high - low ) / 2;
        
   merge_sort(unsorted_array, low, mid);
   merge_sort(unsorted_array, mid+1, high);
        
   merge(unsorted_array, low, mid, high);

}

其中 high 包含在内，您可以这样称呼它：merge_sort(arr, 0, arr.length-1)

Answer 2

你犯了一个很简单的错误。

您的代码中以下两行是错误的：

merge_sort(first_array);
merge_sort(second_array);

这两行你应该写成如下：

first_array = merge_sort(first_array);
second_array = merge_sort(second_array);

因为，你的 merge_sort() 方法 returns 一个 排序数组。它不会对 unsorted_array 参数进行排序。相反，它 return 是新创建的 sorted_array 中的已排序元素。因此，您将从 merge_sort() 方法的 return 值获得排序结果，然后，您应该合并它们。您没有这样做，而是合并了两个未排序的数组。

不是必须的，但你可以写成下面这样来说明：

int[] sorted_first_array = merge_sort(first_array);
int[] sorted_second_array = merge_sort(second_array);
// and then merge
int[] sorted_array = merge(sorted_first_array, sorted_second_array);
// then return
return sorted_array;

[P.S.]：当您在java中编码时，请使用java变量和方法命名约定。当您遵循约定时，它更容易阅读代码。

合并排序无法正常工作。数组中的数字未排序

Merge Sort does not work properly. The numbers in array are not sorted

java

arrays

sorting

algorithm

mergesort