Java 运行时堆排序程序错误
Java heapsort program error during runtime
我的代码在编译期间可以正常工作,但运行时错误指向我的 MaxHeapify
函数中的 if 条件。我标出来了。任何帮助都会非常可爱,并且会让我不再用头撞墙。
public class HeapSort {
public static void main(String[] args) {
int A[] = {-100, 1, 2, 5, 7, 2, 9};
Heapsort(A);
//System.out.println(A.length);
for (int x = 1; x < A.length; x++) {
System.out.println(A[x] + " ");
}
}
public static void Build_MAX_heap(int A[]) {
int n = A.length;
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
}
public static void MAX_heapify(int A[], int i) {
int heapsize = A.length;
int l = 2 * i;
int r = 2 * i + 1;
//find the largest of A[i].A[l],A[r]
int largest = i;
if (A[l] > A[largest]) {
largest = l;
if (A[l] > A[largest] && l <= heapsize) {
largest = l;
}
if (A[r] > A[largest] && r <= heapsize) { //runtime error here
largest = r;
}
if (largest != i) {
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_heapify(A, largest);
}
}
}
public static void Heapsort(int A[]) {
Build_MAX_heap(A);
int heapsize = A.length;
for (int last = heapsize; last >= 2; last--) {
int temp = A[1];
A[1] = A[last];
A[last] = temp;
heapsize--;
MAX_heapify(A,1);
}
}
}
您正在对 r
(以及 l
,也在前面的语句中进行边界检查)after 检查索引 r
。如果 r 越界,表达式的前半部分将抛出异常,永远不会进入边界检查。
你的 if 语句应该是结构化的
if (r < heapsize && A[r] > A[largest]) ...
这样您就可以在开始尝试访问您的阵列之前知道自己在边界内。此外,由于数组是零索引的,heapsize
的索引无效,因此 r
需要小于,而不是小于或等于。
变量 r
设置为:
int r = 2 * i + 1;
第一种循环情况:
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
i
是 n/2
所以要传递的函数是:
MAX_heapify(A,n/2);
和 r
是 2 * (n/2) + 1
即 n+1
当你想做这行的时候
if (A[r] > A[largest] && r <= heapsize) {
然后 A[r]
是 A[n+1]=A[A.length+1]
- 这导致 IndexOutOfBoundsException
你的问题是你在检查 r 是否超出范围之前先检查 A[r]
所以我会尝试以这种方式修改代码
public class HeapSort {
public static void main(String[] args) {
int A[] = {-100, 1, 2, 5, 7, 2, 9};
Heapsort(A);
//System.out.println(A.length);
for (int x = 1; x < A.length; x++) {
System.out.println(A[x] + " ");
}
}
public static void Build_MAX_heap(int A[]) {
int n = A.length;
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
}
public static void MAX_heapify(int A[], int i) {
int heapsize = A.length;
int l = 2 * i;
int r = 2 * i + 1;
//find the largest of A[i].A[l],A[r]
int largest = i;
if (A[l] > A[largest]) {
largest = l;
if (A[l] > A[largest] && l <= heapsize) {
largest = l;
}
if (r<=heapsize && A[r] > A[largest]) { //modification here
largest = r;
}
if (largest != i) {
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_heapify(A, largest);
}
}
}
public static void Heapsort(int A[]) {
Build_MAX_heap(A);
int heapsize = A.length;
for (int last = heapsize; last >= 2; last--) {
int temp = A[1];
A[1] = A[last];
A[last] = temp;
heapsize--;
MAX_heapify(A,1);
}
}
}
我的代码在编译期间可以正常工作,但运行时错误指向我的 MaxHeapify
函数中的 if 条件。我标出来了。任何帮助都会非常可爱,并且会让我不再用头撞墙。
public class HeapSort {
public static void main(String[] args) {
int A[] = {-100, 1, 2, 5, 7, 2, 9};
Heapsort(A);
//System.out.println(A.length);
for (int x = 1; x < A.length; x++) {
System.out.println(A[x] + " ");
}
}
public static void Build_MAX_heap(int A[]) {
int n = A.length;
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
}
public static void MAX_heapify(int A[], int i) {
int heapsize = A.length;
int l = 2 * i;
int r = 2 * i + 1;
//find the largest of A[i].A[l],A[r]
int largest = i;
if (A[l] > A[largest]) {
largest = l;
if (A[l] > A[largest] && l <= heapsize) {
largest = l;
}
if (A[r] > A[largest] && r <= heapsize) { //runtime error here
largest = r;
}
if (largest != i) {
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_heapify(A, largest);
}
}
}
public static void Heapsort(int A[]) {
Build_MAX_heap(A);
int heapsize = A.length;
for (int last = heapsize; last >= 2; last--) {
int temp = A[1];
A[1] = A[last];
A[last] = temp;
heapsize--;
MAX_heapify(A,1);
}
}
}
您正在对 r
(以及 l
,也在前面的语句中进行边界检查)after 检查索引 r
。如果 r 越界,表达式的前半部分将抛出异常,永远不会进入边界检查。
你的 if 语句应该是结构化的
if (r < heapsize && A[r] > A[largest]) ...
这样您就可以在开始尝试访问您的阵列之前知道自己在边界内。此外,由于数组是零索引的,heapsize
的索引无效,因此 r
需要小于,而不是小于或等于。
变量 r
设置为:
int r = 2 * i + 1;
第一种循环情况:
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
i
是 n/2
所以要传递的函数是:
MAX_heapify(A,n/2);
和 r
是 2 * (n/2) + 1
即 n+1
当你想做这行的时候
if (A[r] > A[largest] && r <= heapsize) {
然后 A[r]
是 A[n+1]=A[A.length+1]
- 这导致 IndexOutOfBoundsException
你的问题是你在检查 r 是否超出范围之前先检查 A[r] 所以我会尝试以这种方式修改代码
public class HeapSort {
public static void main(String[] args) {
int A[] = {-100, 1, 2, 5, 7, 2, 9};
Heapsort(A);
//System.out.println(A.length);
for (int x = 1; x < A.length; x++) {
System.out.println(A[x] + " ");
}
}
public static void Build_MAX_heap(int A[]) {
int n = A.length;
for (int i = n / 2; i >= 1; i--) {
MAX_heapify(A, i);
}
}
public static void MAX_heapify(int A[], int i) {
int heapsize = A.length;
int l = 2 * i;
int r = 2 * i + 1;
//find the largest of A[i].A[l],A[r]
int largest = i;
if (A[l] > A[largest]) {
largest = l;
if (A[l] > A[largest] && l <= heapsize) {
largest = l;
}
if (r<=heapsize && A[r] > A[largest]) { //modification here
largest = r;
}
if (largest != i) {
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_heapify(A, largest);
}
}
}
public static void Heapsort(int A[]) {
Build_MAX_heap(A);
int heapsize = A.length;
for (int last = heapsize; last >= 2; last--) {
int temp = A[1];
A[1] = A[last];
A[last] = temp;
heapsize--;
MAX_heapify(A,1);
}
}
}