Merge-Sort 实现 / 怀疑递归调用或合并过程中出现错误

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

Merge-Sort implementation / suspecting mistake in recursive call or while merging

问题

任何对这个混乱的帮助都会被赞赏。这里的任务是对一个不包含零的整数数组进行排序。我认为我犯了两个错误,但我无法解决。

第一:我认为在递归调用时犯了一个错误。合并时似乎设置了错误的边界。

第二:我也认为排序过程中存在多个错误。

static void mergeSort(int[] init, int lower, int upper) {
    if (lower < upper) {

        int mid = (lower + upper) / 2;
        mergeSort(init, lower, mid);
        mergeSort(init, mid+1, upper);
        merge(init, lower, mid, upper);
    }
}

static void merge(int[] init, int lower, int mid, int upper) {
    int length1 = mid - lower;      //第一个子数组的长度
    int length2 = upper - mid;      //第二个子数组的长度

    int[] leftArray = new int[length1+1];     //创建左子数组
    int[] rightArray = new int[length2+1];    //创建右子数组

    for (int i = 0; i < length1; i++) {       //将左分区的位置复制到左子数组
        leftArray[i] = init[lower + i];
    }

    for (int i = 0; i < length2; i++) {       //将右分区的位置复制到右子数组
        rightArray[i] = init[mid+i+1]; //注意这里要加1,因为mid包含在左子数组中
    }

    int i = 0;                                
    int j = 0;
    for (int k = lower; k < upper; k++) {
        if (i < length1 && (j >= length2 || leftArray[i] <= rightArray[j])) { //添加了对i和j的边界检查
            init[k] = leftArray[i];
            i++;
        } else {
            init[k] = rightArray[j];
            j++;
        }
    }
}

希望这有助于解决你的问题。

英文:

any help with this mess is appreciated. The task here is to sort an array of integers that differ from zero. I think i made two mistakes which i cant manage to solve.

first: i think i made a mistake at the recursive call. The bounds seem to be set the wrong way while merging

second: i also think the sorting process has several errors too

    static void mergeSort(int[] init, int lower, int upper) {
if (lower &lt; upper) {
int mid = (lower + upper) / 2;
mergeSort(init, lower, mid);
mergeSort(init, mid+1, upper);
merge(init, lower, mid, upper);
}
}
static void merge(int[] init, int lower, int mid, int upper) {
int length1 = mid - lower;      //length of first subarray
int length2 = upper - mid;      //length of second subarray
int[] leftArray = new int[length1+1];     //creating left subArray
int[] rightArray = new int[length2+1];    //creating right subArray
for (int i = 0; i &lt; length1; i++) {       //copying positions from left partition to left subArray
leftArray[i] = init[lower + i];
}
for (int i = 0; i &lt; length2; i++) {       //copying positions from right partition to right subArray
rightArray[i] = init[mid+i];
}
int i = 0;                                //sorting
int j = 0;
for (int k = lower; k &lt; upper; k++) {
if (leftArray[i] &lt;= rightArray[j]) {
init[k] = leftArray[i];
i++;
} else {
init[k] = rightArray[j];
j++;
}
}
}

答案1

得分: 0

这是使用静态方法逐步执行归并排序的推荐方法吗:

public static void mergeSort(int[] init, int arrayLength) {
    if (arrayLength < 2) {
        return;
    }
    int mid = arrayLength / 2;
    int[] left = new int[mid];
    int[] right = new int[arrayLength - mid];
 
    for (int i = 0; i < mid; i++) {
        left[i] = init[i];
    }
    for (int i = mid; i < arrayLength; i++) {
        right[i - mid] = init[i];
    }
    mergeSort(left, mid);
    mergeSort(right, arrayLength - mid);
 
    merge(init, left, right, mid, arrayLength - mid);
}

public static void merge(
  int[] init, int[] left, int[] right, int leftLength, int rightLength) {
 
    int i = 0, j = 0, k = 0;
    while (i < leftLength && j < rightLength) {
        if (left[i] <= right[j]) {
            init[k++] = left[i++];
        }
        else {
            init[k++] = right[j++];
        }
    }
    while (i < leftLength) {
        init[k++] = left[i++];
    }
    while (j < rightLength) {
        init[k++] = right[j++];
    }
}

调用 "mergeSort",第一个参数是要排序的数组,第二个参数是它的长度。

祝好!

英文:

Wasn't this the recommended way to do the merge sort step-by-step using static methods:

public static void mergeSort(int[] init, int arrayLength) {
if (arrayLength &lt; 2) {
return;
}
int mid = arrayLength / 2;
int[] left = new int[mid];
int[] right = new int[arrayLength - mid];
for (int i = 0; i &lt; mid; i++) {
left[i] = init[i];
}
for (int i = mid; i &lt; arrayLength; i++) {
right[i - mid] = init[i];
}
mergeSort(left, mid);
mergeSort(right, arrayLength - mid);
merge(init, left, right, mid, arrayLength - mid);
}
public static void merge(
int[] init, int[] left, int[] right, int leftLength, int rightLength) {
int i = 0, j = 0, k = 0;
while (i &lt; leftLength &amp;&amp; j &lt; rightLength) {
if (left[i] &lt;= right[j]) {
init[k++] = left[i++];
}
else {
init[k++] = right[j++];
}
}
while (i &lt; leftLength) {
init[k++] = left[i++];
}
while (j &lt; rightLength) {
init[k++] = right[j++];
}
}

Call "mergeSort" with the 1st parameter being the array to be sorted and the 2nd parameter being it's length.

Cheers!

huangapple
  • 本文由 发表于 2020年7月31日 21:06:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/63192439.html
匿名

发表评论

匿名网友

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

确定