java中使合并排序只使用(n/2+1)额外空间的算法
我试图使合并排序只使用(n/2+1)额外的空间和O(n logn)时间。这是我的家庭作业
最初的问题是:
Write the non-recursive version of merge sort. Your program should run in O(n log n) time and use n/2 + O(1) extra spaces.
该程序将把一个数组一分为二,就像普通的合并排序一样
左侧部分将位于另一个数组中,该数组的长度为ceil(n/2),因此它将符合要求
正确的部分将位于原始阵列中。因此,它将是半就地排序
对不起,我不知道如何进一步解释
我认为这基本上是正确的。但我一直在面对边界外的错误
我知道代码很长很乱。有人能帮我吗
我花了大约5个小时来实现这个。请帮帮我
package comp2011.lec6;
import java.util.Arrays;
public class MergeSort {
public static void printArr(int[] arr){
for(int i = 0; i < arr.length; i++){
System.out.printf("%d ", arr[i]);
}
}
public static void mergeSort(int[] arr){
if(arr.length<2) {
return;
}
int n, lBegin, rBegin;
n = 1;
int[] leftArr = new int[arr.length - (arr.length/2)];
while(n<arr.length) {
lBegin = 0;
rBegin = n;
while(rBegin + n <= arr.length) {
mergeArrays(arr, lBegin, lBegin+n, rBegin, rBegin+n, leftArr);
lBegin = rBegin+n;
rBegin = lBegin+n;
}
if(rBegin < arr.length) {
mergeArrays(arr, lBegin, lBegin+n, rBegin, arr.length, leftArr);
}
n = n*2;
}
}
public static void mergeArrays(int[] array, int startL, int stopL, int startR, int stopR, int[] leftArr) {
// int[] right = new int[stopR - startR + 1];
// int[] left = new int[stopL - startL + 1];
// for(int i = 0, k = startR; i < (right.length - 1); ++i, ++k) {
// right[i] = array[k];
// }
System.out.println("==============");
System.out.println("stopL: " + stopL +" startL: " + startL);
for(int i = 0, k = startL; i <= (stopL - startL); ++i, ++k) {
System.out.println(leftArr[i]);
leftArr[i] = array[k];
}
// right[right.length-1] = Integer.MAX_VALUE;
leftArr[stopL - startL] = Integer.MAX_VALUE;
System.out.println("leftArr: " + Arrays.toString(leftArr));
System.out.println("RightArr: " + Arrays.toString(Arrays.copyOfRange(array, startR, stopR)));
System.out.println("before: " + Arrays.toString(array));
// for(int k = startL, m = 0, n = startR; k < stopR; ++k) {
System.out.println("StartL: " + startL + " StartR: " + stopR);
for(int k = startL, m = 0, n = startR; ( (k < stopR) ); ++k) {
System.out.println("k: " + k);
System.out.println("Left: " + leftArr[m]);
System.out.println("Right: " + array[n]);
System.out.println("Array[k] before: " + array[k]);
// if(leftArr[m] == Integer.MAX_VALUE){
// System.out.println("YES");
// }
if( (leftArr[m] <= array[n]) || (n >= stopR) ) {
System.out.println("Left is smaller than right");
array[k] = leftArr[m];
m++;
}
else {
System.out.println("Right is smaller than left");
array[k] = array[n];
System.out.println("right: " + array[k]);
n++;
}
System.out.println("Array[k] after: " + array[k]+"\n");
}
System.out.println("after " + Arrays.toString(array));
}
public static void main(String[] args) {
int[] array = new int[] { 5, 2, 4, 12, 2, 10, 13, 1, 7 };
mergeSort(array);
printArr(array);
}
}
共 (0) 个答案