合并排序Java [英] Merge Sort Java
问题描述
我正在尝试创建一个合并排序方法，但它继续给出错误的排序。我在哪里进行更改以使其实际排序数组？代码的哪一部分必须不同？感谢您的时间。
I am trying to make a merge sort method, but it keeps on giving the wrong sorts. Where do I have change to make it actually sort the array? What part of the code has to be different? Thank you for your time.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= array[right]) {
temp[num] = array[left];
left++;
}
else {
temp[num] = array[right];
right++;
}
num++;
}
while (left <= right){
temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = array[right];
right += 1;
num += 1;
}
for (int i=0; i < elements; i++){
array[rHigh] = temp[rHigh];
rHigh -= 1;
}
编辑：现在mergeSort没有对数字进行真正排序，有人可以告诉我特意在哪里？特别是当我打印测试合并排序部分时。
now the mergeSort doesn't really sort the numbers, can someone tell me where it specifically is? especially when I print the "Testing merge sort" part.
推荐答案
首先，我假设这是学术性的而不是实际的，因为你没有使用内置的排序功能。话虽如此，这里有一些帮助让你朝着正确的方向前进：
First of all, I'm assuming this is academic rather than practical, since you're not using a built in sort function. That being said, here's some help to get you moving in the right direction:
通常，可以将合并排序视为两种不同的方法：merge（）函数将两个排序列表合并为一个排序列表，mergeSort（）将列表递归地拆分为单个元素列表。由于已经对单个元素列表进行了排序，然后将所有列表合并为一个大的排序列表。
Usually, one can think of a merge sort as two different methods: a merge() function that merges two sorted lists into one sorted list, and mergeSort() which recursively breaks the list into single element lists. Since a single element list is sorted already, you then merge all the lists together into one big sorted list.
这里有一些副手伪代码：
Here's some off-hand pseudo-code:
merge(A, B):
C = empty list
While A and B are not empty:
If the first element of A is smaller than the first element of B:
Remove first element of A.
Add it to the end of C.
Otherwise:
Remove first element of B.
Add it to the end of C.
If A or B still contains elements, add them to the end of C.
mergeSort(A):
if length of A is 1:
return A
Split A into two lists, L and R.
Q = merge(mergeSort(L), mergeSort(R))
return Q
也许这有助于清理你想去的地方。
Maybe that'll help clear up where you want to go.
如果没有，总是 MergeSort 。
其他：
为了帮助您，以下是您的代码内联的一些注释。
To help you out, here are some comments inline in your code.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// what do lHigh and rHigh represent?
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
// what does this while loop do **conceptually**?
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= a[right]) {
// where is 'pos' declared or defined?
temp[pos] = a[left];
// where is leftLow declared or defined? Did you mean 'left' instead?
leftLow ++;
}
else {
temp[num] = a[right];
right ++;
}
num++;
}
// what does this while loop do **conceptually**?
while (left <= right){
// At this point, what is the value of 'num'?
temp[num] = a[left];
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = a[right];
right += 1;
num += 1;
}
// Maybe you meant a[i] = temp[i]?
for (int i=0; i < elements; i++){
// what happens if rHigh is less than elements at this point? Could
// rHigh ever become negative? This would be a runtime error if it did
a[rHigh] = temp[rHigh];
rHigh -= 1;
}
我故意模糊，所以你要考虑算法。尝试将自己的注释插入代码中。如果你可以写出概念上发生的事情，那么你可能不需要Stack Overflow：）
I'm purposefully being vague so you think about the algorithm. Try inserting your own comments into the code. If you can write what is conceptually happening, then you may not need Stack Overflow :)
我的想法是你没有正确实现这一点。这是因为看起来你只触摸一次数组元素（或只接近一次）。这意味着您遇到了最糟糕的情况： O（N）排序通常至少需要 O（N * log N）据我所知，更简单的合并排序版本实际上是 O（N ^ 2） 。
My thoughts here are that you are not implementing this correctly. This is because it looks like you're only touching the elements of the array only once (or close to only once). This means you have a worst case scenario of O(N) Sorting generally takes at least O(N * log N) and from what I know, the simpler versions of merge sort are actually O(N^2).
更多：
在最简单的合并排序实现中，我期望在mergeSort（）方法中看到某种递归。这是因为合并排序通常是递归定义的。有一些方法可以使用for和while循环迭代地执行此操作，但我绝对不建议它作为一种学习工具，直到你递归地得到它。
In the most simplistic implementation of merge sort, I would expect to see some sort of recursion in the mergeSort() method. This is because merge sort is generally defined recursively. There are ways to do this iteratively using for and while loops, but I definitely don't recommend it as a learning tool until you get it recursively.
老实说，我建议我可以在维基百科文章中找到我的伪代码或伪代码来实现这一点并重新开始使用代码。如果你这样做并且它仍然无法正常工作，请在此处发布，我们将帮助您解决问题。
Honestly, I suggest taking either my pseudo-code or the pseudo-code you may find in a wikipedia article to implement this and start over with your code. If you do that and it doesn't work correctly still, post it here and we'll help you work out the kinks.
干杯！
最后：
// Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
// Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// temp[] needs to be as large as the number of elements you're sorting (not half!)
//int elements = (rHigh - lHigh +1) ;
int elements = rHigh - left;
int[] temp = new int[elements];
// this is your index into the temp array
int num = left;
// now you need to create indices into your two lists
int iL = left;
int iR = right;
// Pseudo code... when you code this, make use of iR, iL, and num!
while( temp is not full ) {
if( left side is all used up ) {
copy rest of right side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if ( right side is all used up) {
copy rest of left side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if (array[iL] < array[iR]) { ... }
else if (array[iL] >= array[iR]) { ... }
}
}
这篇关于合并排序Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
