我正在设置合并排序来对数组进行排序。目标是对任意长度的数组进行排序。
我试过查看mergesort函数,但没有发现任何问题。排序适用于某些数组长度,无论是奇数还是偶数,但对于数组长度,例如长度为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添加了一个if语句,以避免跨越数组边界
if(mid<high) {
merge(A, temp, from, mid, to);
}
完整代码:
// 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);
//System.out.println("temp Array : " + Arrays.toString(temp));
// 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);
if(mid<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=im-1
到
int mid=Math。最小值(i m-1,A.长度-1)
说明:正如您在评论中提到的,您正在检查的区域的切片大小正在增加。下面是数组的排序方式,以及发生越界错误的时间,以及为什么在2次方的大小上没有发生越界错误:
[ -9, 5, 7, 3, -4, 2, 8, 8, 10, 11 ] Array size
First pass: [] [] [] [] [] [] [] [] [] [] 1
Second: [ ] [ ] [ ] [ ] [ ] 2
Third: [ ] [ ] [ ERROR] 4
我从这里得到了帮助,但我特别不想宣布我的方法无效。任何帮助都将不胜感激! 这是我的合并排序的实现,我得到的输出是5 4 3 2 1 10 9 8 7 6。 有人能帮我弄清楚我该怎么做吗? 我不想将mergesort和merge方法声明为void,而是希望它们返回排序后的数组。提前谢谢。
我第一次用一个辅助数组实现了合并排序,以尝试使用JavaScript实现可视化。这似乎应该是有效的,但它不是。任何帮助或提示将不胜感激。 编辑:我忘了包括它不起作用的情况。它们是: 输入:[4, 2, 5, 6, 7, 7]输出:[4, 2, 5, 6, 7, 7] 输入:[6,6,6,4,6,2]输出:[4,6,6,6,6,2] 输入:[6, 7, 3, 10, 7, 9, 6, 3, 4, 6
我基本上理解了包含数组、低整数和高整数的递归合并排序函数。然而,我很好奇地试图编写一个只包含数组长度的递归合并排序函数。签名是:这比我想象的要困难得多。 我将在下面发布代码,但我的函数(我认为)只是为每次调用merge_sort()拆分数组的前半部分,本质上不涉及数组的后半部分(我认为也是如此)。 我遇到的另一个问题是,当将所有内容从辅助数组复制回原始数组(使用for循环)时,我不确定使用什么作为
我在计算机课上遇到了合并排序的问题。我不断收到错误或返回原始ArrayList。 我相信合并排序涉及到将数组(列表)递归地对半拆分,直到只剩下一个元素,然后从这些单独的元素开始,按排序顺序合并它们。直到数组(列表)被排序为止。至于实际的排序部分,我试图在新的ArrayList中插入两半之间的较高值,直到它们都为空,在这种情况下,填充的ArrayList现在被排序。 这是我当前的代码: 我将感谢任何
问题内容: 我做了一个字谜游戏机,并且有一系列正面匹配。麻烦的是它们都以不同的顺序排列,我希望能够对数组进行排序,以使最长的数组值首先出现。 有人对如何执行此操作有任何想法吗? 问题答案: 使用http://us2.php.net/manual/en/function.usort.php 使用此自定义功能 如果要保留旧索引,请使用uasort;如果您不关心,请使用usort。 另外,我认为我的版本
本文向大家介绍z-index有时不起作用的原因是什么?怎么解决?相关面试题,主要包含被问及z-index有时不起作用的原因是什么?怎么解决?时的应答技巧和注意事项,需要的朋友参考一下 1、可能是没有设置position 解决:设置position为relative,absolute,fixed 2、设置了浮动 解决:清除浮动 3、父元素position为relative 解决:设置为absolut