合并排序Java
我正在尝试创建一个合并排序方法，但它继续给出错误的排序。 我在哪里进行更改以使其实际排序数组？ 代码的哪一部分必须不同？ 感谢您的时间。
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没有真正排序数字，有人可以告诉我具体是什么？ 特别是当我打印“测试合并排序”部分时。
首先，我假设这是学术性的而不是实用的，因为你没有使用内置的排序function。 话虽如此，这里有一些帮助，让你朝着正确的方向前进：
通常，可以将合并排序视为两种不同的方法：将两个排序列表合并为一个排序列表的merge（）函数，以及递归地将列表拆分为单个元素列表的mergeSort（）。 由于已经对单个元素列表进行了排序，因此您将所有列表合并为一个大的排序列表。
这是一些副手伪代码：
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
也许这有助于清理你想去的地方。
如果没有，维基百科上总会有MergeSort 。
附加 ：
为了帮助您，以下是您的代码内联的一些注释。
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 🙂
我的想法是你没有正确实现这一点。 这是因为看起来你只触摸一次数组元素（或只接近一次）。 这意味着你有一个最糟糕的情况O（N）排序通常需要至少O(N * log N) ，据我所知，合并排序的简单版本实际上是O(N^2) 。
更多：
在最简单的合并排序实现中，我希望在mergeSort（）方法中看到某种递归 。 这是因为合并排序通常是递归定义的。 有一些方法可以使用for和while循环迭代地执行此操作，但在您递归获取之前，我绝对不建议将其作为学习工具。
老实说，我建议您使用我在伪维基文章中找到的伪代码或伪代码来实现这一点并重新开始使用您的代码。 如果你这样做并且它仍然无法正常工作，请在此处发布，我们将帮助您解决问题。
干杯!
最后：
// 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]) { ... } } }
public class MergeSort { public static void main(String[] args) { int[] arr = {5, 4, 7, 2, 3, 1, 6, 2}; print(arr); new MergeSort().sort(arr, 0, arr.length - 1); } private void sort(int[] arr, int lo, int hi) { if (lo < hi) { int mid = (lo + hi) / 2; sort(arr, lo, mid); // recursive call to divide the sub-list sort(arr, mid + 1, hi); // recursive call to divide the sub-list merge(arr, lo, mid, hi); // merge the sorted sub-lists. print(arr); } } private void merge(int[] arr, int lo, int mid, int hi) { // allocate enough space so that the extra 'sentinel' value // can be added. Each of the 'left' and 'right' sub-lists are pre-sorted. // This function only merges them into a sorted list. int[] left = new int[(mid - lo) + 2]; int[] right = new int[hi - mid + 1]; // create the left and right sub-list for merging into original list. System.arraycopy(arr, lo, left, 0, left.length - 1); System.arraycopy(arr, mid + 1, right, 0, left.length - 1); // giving a sentinal value to marking the end of the sub-list. // Note: The list to be sorted is assumed to contain numbers less than 100. left[left.length - 1] = 100; right[right.length - 1] = 100; int i = 0; int j = 0; // loop to merge the sorted sequence from the 2 sub-lists(left and right) // into the main list. for (; lo <= hi; lo++) { if (left[i] <= right[j]) { arr[lo] = left[i]; i++; } else { arr[lo] = right[j]; j++; } } } // print the array to console. private static void print(int[] arr) { System.out.println(); for (int i : arr) { System.out.print(i + ", "); } } }
这是另一个！
private static int[] mergeSort(int[] input){ if (input.length == 1) return input; int length = input.length/2; int[] left = new int[length]; int[] right = new int[input.length - length]; for (int i = 0; i < length; i++) left[i] = input[i]; for (int i = length; i < input.length; i++) right[i-length] = input[i]; return merge(mergeSort(left),mergeSort(right)); } private static int[] merge(int[] left, int[] right){ int[] merged = new int[left.length+right.length]; int lengthLeft = left.length; int lengthRight = right.length; while (lengthLeft > 0 && lengthRight > 0){ if (left[left.length - lengthLeft] < right[right.length - lengthRight]){ merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft]; lengthLeft--; }else{ merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight]; lengthRight--; } } while (lengthLeft > 0){ merged[merged.length - lengthLeft] = left[left.length-lengthLeft]; lengthLeft--; } while (lengthRight > 0){ merged[merged.length - lengthRight] = right[right.length-lengthRight]; lengthRight--; } return merged; }
static void mergeSort(int arr[],int p, int r) { if(p
>
使用Sentinel合并排序
这段代码完美无缺。
public void mergeSort(int a[], int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(a, low, mid); mergeSort(a, mid + 1, high); merge(a, low, mid, high); } } public void merge(int a[], int low, int mid, int high) { int n1 = mid - low + 1;// length of an array a1 int n2 = high - mid; // length of an array a2 int a1[] = new int[n1 + 1]; int a2[] = new int[n2 + 1]; int lowRange = low; for (int i = 0; i < n1; i++) { a1[i] = a[lowRange]; lowRange++; } for (int j = 0; j < n2; j++) { a2[j] = a[mid + j + 1]; } a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1 a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2 int i = 0; int j = 0; int k = low; for (k = low; k <= high; k++) { if (a1[i] >= a2[j]) { a[k] = a2[j]; j++; } else { a[k] = a1[i]; i++; } } if (a2.length >= a1.length) { for (int ab = k; ab < a2.length; ab++) { a[k] = a2[ab]; k++; } } else if (a1.length >= a2.length) { for (int ab = k; ab < a1.length; ab++) { a[k] = a1[ab]; k++; } } }
这是另一种选择：
public class MergeSort { public static void merge(int[]a,int[] aux, int f, int m, int l) { for (int k = f; k <= l; k++) { aux[k] = a[k]; } int i = f, j = m+1; for (int k = f; k <= l; k++) { if(i>m) a[k]=aux[j++]; else if (j>l) a[k]=aux[i++]; else if(aux[j] > aux[i]) a[k]=aux[j++]; else a[k]=aux[i++]; } } public static void sort(int[]a,int[] aux, int f, int l) { if (l<=f) return; int m = f + (lf)/2; sort(a, aux, f, m); sort(a, aux, m+1, l); merge(a, aux, f, m, l); } public static int[] sort(int[]a) { int[] aux = new int[a.length]; sort(a, aux, 0, a.length-1); return a; }
}
包com;
public class Test { int count = 0; public static void main(String[] args) { int a[] = {1,3,5,7,9,10,14,15,16}; int b[] = {2,4,6,8,11,12,13,17,18}; int sizec = a.length+b.length; int c[] = new int[sizec]; int i=0;int j=0;int k=0; while(kb[j] ) { c[k]=b[j]; j++; } else if(a[i]