Merge Sort不正常工作。数组中的数字没有排序。

huangapple go评论47阅读模式
英文:

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

问题

以下是您的Merge Sort JAVA代码的翻译:

以下是我的Merge Sort 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];
        
        //将元素复制到第一个和第二个数组中。
        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;
    }

merge方法:

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;
    }

希望这可以帮助您解决问题。

英文:

The following is my code for Merge Sort in JAVA, but the output is not expected.

given input is [49, 1, 3, 200, 2, 4, 70, 5]

The output is :

Merge sort : [2, 4, 49, 1, 3, 70, 5, 200]

Which the number is not sorted. I believe the problem is in the merge method. Can anyone help?

merge_sort method:

private static int[] merge_sort(int[] unsorted_array) {
		
		if (unsorted_array.length &lt; 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 &lt; mid; i ++) {
			
			first_array[i] = unsorted_array[i];
		}
		
		for (int i = 0; i &lt; 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;
	}

merge method:

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 &lt; first_array.length &amp;&amp; index_second &lt; second_array.length) {
			
			if (first_array[index_first] &lt; 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 &lt; first_array.length) {
			
			result[index_result] = first_array[index_first];
			index_result++;
			index_first++;
		}
		
		while (index_second &lt; second_array.length) {
			
			result[index_result] = second_array[index_second];
			index_result++;
			index_second++;
		}
		
		return result;
	}

答案1

得分: 0

你没有使用排序后的中间结果来合并,而是使用原始分割的数组。请按以下方式修改你的代码:

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)`
英文:

You are not using the sorted intermediate results to merge, instead using the original splitted arrays. Modify your code as below:

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

Also you don't need to create these intermediate arrays. You just have to pass the low, high pointers to your array to indicate the portions of the array you are sorting and merging.

Like :

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);

}

where high is inclusive and you call this like : merge_sort(arr, 0, arr.length-1)

答案2

得分: 0

你犯了一个非常简单的错误。

你代码中以下两行是错误的:

merge_sort(first_array);
merge_sort(second_array);

你应该将这两行改为如下:

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

因为你的 merge_sort() 方法 返回 一个 排序后的数组。它不会直接对 unsorted_array 参数进行原地排序,而是返回一个新创建的 sorted_array 中排序后的元素。所以,你应该从 merge_sort() 方法的返回值中获取排序后的结果,然后再进行合并。而你之前只是在合并两个未排序的数组。

这不是必需的,但为了更清晰,你可以这样写:

int[] sorted_first_array = merge_sort(first_array);
int[] sorted_second_array = merge_sort(second_array);
// 然后合并
int[] sorted_array = merge(sorted_first_array, sorted_second_array);
// 然后返回
return sorted_array;
英文:

You've made a very simple mistake.

Those two following lines are wrong in your code:

merge_sort(first_array);
merge_sort(second_array);

You should write those two lines as follows:

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

cause, your merge_sort() method returns a sorted array. It does not sort in place the unsorted_array parameter. Rather, it returns the sorted elements in a newly created sorted_array. So, you would get the sorted result from return value of merge_sort() method and then, you should merge them. Rather than doing that, you were just merging two unsorted arrays.

Its not necessary, but you could write as follows for clarification:

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.]: When you are coding in java, please use java variable and method naming convention. Its easier to read code when you're following convention.

huangapple
  • 本文由 发表于 2020年7月28日 17:28:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/63131039.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定