gpt4 book ai didi

java - 我的合并排序对于数组长度 10 不起作用是否有原因

转载 作者:行者123 更新时间:2023-12-02 10:06:29 27 4
gpt4 key购买 nike

我正在设置合并排序来对我的数组进行排序。目标是对任意长度的数组进行排序。

我尝试查看合并排序函数,但我没有发现它有任何问题。该排序适用于某些数组长度(无论是奇数还是偶数),但对于数组长度(例如长度为 10),我会遇到越界异常。

import java.util.Arrays;

class MergeSort
{
// Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to]
public static void merge(int[] A, int[] temp, int from, int mid, int to)
{
int k = from, i = from, j = mid + 1;

// loop till there are elements in the left and right runs
while (i <= mid && j <= to) {
if (A[i] < A[j]) {
temp[k++] = A[i++];
} else {
temp[k++] = A[j++];
}
}

// Copy remaining elements
while (i <= mid) {
temp[k++] = A[i++];
}

// Don't need to copy second half

// copy back to the original array to reflect sorted order
for (i = from; i <= to; i++) {
A[i] = temp[i];
}
}

// Iteratively sort array A[low..high] using temporary array
public static void mergesort(int[] A)
{
int low = 0;
int high = A.length - 1;

// sort array A[] using temporary array temp
int[] temp = Arrays.copyOf(A, A.length);

// divide the array into blocks of size m
// m = [1, 2, 4, 8, 16...]
for (int m = 1; m <= high - low; m = 2*m)
{
// for m = 1, i = 0, 2, 4, 6, 8...
// for m = 2, i = 0, 4, 8, 12...
// for m = 4, i = 0, 8, 16...
// ...
for (int i = low; i < high; i += 2*m)
{
int from = i;
int mid = i + m - 1;
int to = Integer.min(i + 2 * m - 1, high);

merge(A, temp, from, mid, to);
}
}
}

// Iterative Implementation of Mergesort algorithm
public static void main(String[] args)
{
int[] A = { 5, 7, -9, 3, -4, 2, 8, 8, 10, 11 };

System.out.println("Original Array : " + Arrays.toString(A));
mergesort(A);
System.out.println("Modified Array : " + Arrays.toString(A));
}
}

最佳答案

您的中间计算不正确。有时您会将其设置在该区域的范围之外。

下面的更改通过防止 mid 出界来修复算法,类似于您防止 to 出界的方法。

更改int mid = i + m - 1;int mid = Math.min(i + m - 1, A.length - 1);

说明:正如您在评论中提到的,您正在检查的区域切片的大小正在增加。以下是数组的排序方式、何时发生越界错误,以及为什么在 2 的幂大小上没有发生该错误:

             [ -9,  5,  7,  3, -4,  2,  8,  8, 10, 11 ]           Array size
First pass: [] [] [] [] [] [] [] [] [] [] 1
Second: [ ] [ ] [ ] [ ] [ ] 2
Third: [ ] [ ] [ ERROR] 4

关于java - 我的合并排序对于数组长度 10 不起作用是否有原因,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55306470/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com