在java中合并排序算法 [英] Merge sort algorithm in java
问题描述
你好！
我想用合并排序算法对数组进行排序。我写了鳕鱼，我的代码中的一切似乎都很好，但结果数组没有正确排序。我要把我的代码放在下面。结果数组是
Hello!
I want to sort an array with the merge sort algorithm. I wrote the cod, everything seems to be fine in my code, but the resulted array is not sorted properly. I am going to put bellow my code. The resulted array is
[2, 55, 22, 22, 44, 66, 33, 77]
提前谢谢。
我的尝试：
Thank you in advance.
What I have tried:
import java.util.Arrays;
/*
Write a function that sorts an array of numbers using merge sort.
*/
public class BonusExtraExercise11 {
public static void main(String[] args) {
int[] unsortedArray = {2, 55, 44, 22, 77,66,33,22};
String sortedArray = Arrays.toString(DivideArray(unsortedArray));
System.out.println(sortedArray);
}
public static int [] DivideArray(int[] unsortedArray) {
// We create two sub-arrays. We give them the value 0. It is going to be changed when we find out if the array
// is even or odd.
if(unsortedArray.length == 1)
{
return unsortedArray; //Array is a single element.
}
int [] leftSide = new int[0];
int [] rightSide = new int[0];
int [] sortedArray;
// We find out if the array is even or odd..
int middle = unsortedArray.length / 2;
int remainder = unsortedArray.length % 2;
// If the array is even the length of the sub-arrays will get the value of the variable "middle".
if(remainder == 0){
leftSide = new int[middle];
rightSide = new int[middle];
}
//If the array is odd than the array leftSide will get the length of the variable middle
//and the rightSide is going to get the value of the variable middle +1.
if(remainder == 1)
{
leftSide = new int[middle];
rightSide = new int[middle+1];
}
//populate leftside
for(int i=0; i<leftSide.length; i++)
{
leftSide[i] = unsortedArray[i];
}
//populate right side
int n=0;
for(int j=middle; j<unsortedArray.length; j++) {
rightSide[n] = unsortedArray[j];
n++;
}
leftSide = DivideArray(leftSide);
rightSide = DivideArray(rightSide);
sortedArray=Merge(leftSide, rightSide);
return sortedArray;
}
public static int [] Merge(int [] leftSide, int [] rightSide)
{
int lengthSortedArray = leftSide.length+rightSide.length;
int [] sortedArray = new int[lengthSortedArray];
int indexL = 0;
int indexR = 0;
int indexSortArr = 0;
while(indexL<leftSide.length || indexR<rightSide.length)
{
if(indexL<leftSide.length && indexR<rightSide.length)
{
if(leftSide[indexL]<=rightSide[indexR])
{
sortedArray[indexSortArr++] = leftSide[indexL++];
}
else
{
sortedArray[indexSortArr++] = rightSide[indexR++];
}
}
if(indexL<leftSide.length)
{
sortedArray[indexSortArr++] = leftSide[indexL++];
}
if(indexR<rightSide.length)
{
sortedArray[indexSortArr++] = rightSide[indexR++];
}
}
return sortedArray;
}
}
推荐答案
我写了鳕鱼，我的代码中的一切似乎都很好，但结果数组没有正确排序。
I wrote the cod, everything seems to be fine in my code, but the resulted array is not sorted properly.
由于结果不正确你的代码中的一切都不好。
一个程序就像英语一样，有一个以上的正确程度。
示例：猫在天空中飞得很高。
- 单词是英语：正确
- 句子语法很好英语：正确
- 这句话没有意义，因为猫不喜欢飞行：不正确
程序编译正常的事实并不意味着它会按预期完成工作。
使用调试器，用于监视代码执行，一步一步地检查变量。调试器是捕获错误的首选工具。
-----
您的代码行为不符合您的预期，您不明白为什么！
有一个几乎通用的解决方案：一步一步地在调试器上运行你的代码，检查变量。
调试器在这里向你展示你的代码正在做什么和你的任务是与它应该做的比较。
调试器中没有魔法，它不知道你应该做什么，它没有找到bug，它只是帮助你告诉你发生了什么。当代码没有达到预期的效果时，你就接近了一个错误。
要查看你的代码在做什么：只需设置断点并查看代码是否正常运行，调试器允许你执行第1行第1行，并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows /jdb.html [ ^ ]
https： //www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]
调试器仅显示您的代码正在执行的操作，您的任务是与什么进行比较应该这样做。
[更新]
Since result is not correct, everything is not fine in your code.
A program is like English, there is more than a single level of correctness.
Example: The cat flies high in the sky.
- The words are English: Correct
- The sentence is syntactically good English: Correct
- The sentence have no meaning because cats don't fly: Not correct
The fact that the program compiles fine does not mean that it will do the job as expected.
Use the debugger to watch your code performing, step by step and inspect the variables. The debugger is the tool of choice to hunt bugs.
-----
Your code do not behave the way you expect, and you don't understand why !
There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.
Debugger - Wikipedia, the free encyclopedia[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]
The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
[Update]
我认为问题在于算法没有对这两个数组进行排序。
I suppose that the problem is that the algorithm doesn't sort the those two arrays.
不要设想，使用调试器来确保。
你的代码很复杂
Do not suppose, use the debugger to make sure.
Your code is complicated
int [] leftSide = new int[0];
int [] rightSide = new int[0];
int [] sortedArray;
// We find out if the array is even or odd..
int middle = unsortedArray.length / 2;
int remainder = unsortedArray.length % 2;
// If the array is even the length of the sub-arrays will get the value of the variable "middle".
if(remainder == 0){
leftSide = new int[middle];
rightSide = new int[middle];
}
//If the array is odd than the array leftSide will get the length of the variable middle
//and the rightSide is going to get the value of the variable middle +1.
if(remainder == 1)
{
leftSide = new int[middle];
rightSide = new int[middle+1];
}
可简化为
can be simplified to
int [] sortedArray;
// We find out if the array is even or odd..
int middle = unsortedArray.length / 2;
int [] leftSide = new int[middle];
int [] rightSide = new int[unsortedArray.length-middle];
[更新]
我看到你的错误
[Update]
I see your error
while(indexL<leftSide.length || indexR<rightSide.length)
{
if(indexL<leftSide.length && indexR<rightSide.length)
{
if(leftSide[indexL]<=rightSide[indexR])
{
sortedArray[indexSortArr++] = leftSide[indexL++];
}
else
{
sortedArray[indexSortArr++] = rightSide[indexR++];
}
}
else
{ // only when you reached the end of leftSide or rightSide
if(indexL<leftSide.length)
{
sortedArray[indexSortArr++] = leftSide[indexL++];
}
if(indexR<rightSide.length)
{
sortedArray[indexSortArr++] = rightSide[indexR++];
}
}
}
这篇关于在java中合并排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
