返回信息流package com.package5;
public class HeapSort {
public static void main(String[] args) {
int[] arr={10,50,30,20,60,80,70,90,40};
System.out.println(arr.length/2);
HSort(arr); //进行排序
for(int i:arr)
System.out.println(i);
}
public static void HSort(int[] a){
int i;
for(i=a.length/2;i>0;i--){
MaxHeap(a,i,a.length); //构建大顶堆
}
for(i=a.length;i>1;i--){
swap(a,1,i);//将堆顶纪录和当前未排序子序列的最后一个纪录交换
MaxHeap(a, 1, i-1); //将a[]数组其余部分重新调整为大顶堆
}
}
public static void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void MaxHeap(int[] a, int s, int m) {
int temp,j;
temp=a[s];
for(j=2*s;j<=m;j*=2){ //沿关键字较大的孩子节点向下筛选
if(j<m&&a[j]<a[j+1]){ //!!!!!!!!报 java.lang.ArrayIndexOutOfBoundsException
++j; //j为关键字中较大纪录的下标
}
if(temp>=a[j]){
break;
}
a[s]=a[j];
s=j;
}
a[s]=temp; //插入数据
}
}
[ema1][ema1][ema1][ema1][ema1]
这是一条镜像帖。来源：北邮人论坛 / java / #52889同步于 2016/9/13
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
[问题]堆排序，数组越界，求指点
ywq956283501
2016/9/13镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
public class HeapSort {
public static void main(String[] args) {
int[] arr={10,50,30,20,60,80,70,90,40};
//System.out.println(arr.length/2);
HSort(arr); //进行排序
for(int i:arr)
System.out.println(i);
}
public static void HSort(int[] a){
int i;
for(i=a.length/2;i>=0;i--){
MaxHeap(a,i,a.length-1); //构建大顶堆【数组越界，应该length-1，不清楚你这个参数是不是】
}
for(i=a.length-1;i>0;i--){ //【还是数组越界问题，length-1】
swap(a,1,i);//将堆顶纪录和当前未排序子序列的最后一个纪录交换
MaxHeap(a, 1, i-1); //将a[]数组其余部分重新调整为大顶堆
}
}
public static void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void MaxHeap(int[] a, int s, int m) {
int temp,j;
temp=a[s];
for(j=2*s;j<m;j*=2){ //沿关键字较大的孩子节点向下筛选
if(j<m && a[j]<a[j+1]){ //【既然有j+1,那么j+1也应该小于等于m，所以j<m】
++j; //j为关键字中较大纪录的下标
}
if(temp>=a[j]){
break;
}
a[s]=a[j];
s=j;
}
a[s]=temp; //插入数据
}
}
不过输出结果还是不大对，没太看明白你是怎么堆排的
我一般是建堆，对里边做堆调整，最后堆排
又改了下，你的用例过了，我的没有。。。
public class HeapSort {
public static void main(String[] args) {
int[] arr={2,9,6,3,5,8,5,2,1,4,6,3,6,9,5,22,55,6,4,5,6,26,29,6,2,9,95,58,45,47,46,25,26,36,62};
//System.out.println(arr.length/2);
int[] arr2={10,50,30,20,60,80,70,90,40};
HSort(arr); //进行排序
HSort(arr2);
//swap(arr,0,1);
for(int i:arr)
System.out.print(i+" ");
System.out.println();
for(int i:arr2)
System.out.print(i+" ");
System.out.println();
}
public static void HSort(int[] a){
int i;
for(i=a.length/2;i>0;i--){
MaxHeap(a,i,a.length-1); //构建大顶堆
}
for(i=a.length-1;i>0;i--){
swap(a,1,i);//将堆顶纪录和当前未排序子序列的最后一个纪录交换
MaxHeap(a, 1, i-1); //将a[]数组其余部分重新调整为大顶堆
}
}
public static void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void MaxHeap(int[] a, int s, int m) {
int temp,j;
temp=a[s];
for(j=2*s;j<=m;j*=2){ //沿关键字较大的孩子节点向下筛选
if(j<m && a[j]<a[j+1]){ //!!!!!!!!报 java.lang.ArrayIndexOutOfBoundsException
++j; //j为关键字中较大纪录的下标
}
if(temp>=a[j]){
break;
}
a[s]=a[j];
s=j;
}
a[s]=temp; //插入数据
}
}
这是我的代码
public class HeapSort{
public void heapAdjust(int[] arr,int i,int size){
int left=2*i+1; //left node
int right=2*i+2; //right node
int largest=i;
if(left<size && arr[i]<arr[left])
largest=left;
if(right<size && arr[right]>arr[largest])
largest=right;
if(largest!=i){
tmp=arr[i];
arr[i]=arr[largest];
arr[largest]=tmp;
heapAdjust(arr,largest,size);
}
}
public void buildHeap(int[] arr,int size){
for(int i=size/2-1;i>=0;i--)
heapAdjust(arr,i,size);
}
public void heapSort(int[] arr){
int size=arr.length;
buildHeap(arr,size);
for(int i=size-1;i>=0;i--){
tmp=arr[0];
arr[0]=arr[i];
arr[i]=tmp;
heapAdjust(arr,0,i);
}
}
public static void main(String[] args){
int[] arr={2,9,6,3,5,8,5,2,1,4,6,3,6,9,5,22,55,6,4,5,6,26,29,6,2,9,95,58,45,47,46,25,26,36,62};
HeapSort hs=new HeapSort();
hs.heapSort(arr);
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
那个我也以为是一个问题，但是试了下反而没问题，关键是他的数组 都是 length 开始swap，这个肯定越界
【 在 mrcuber 的大作中提到: 】
: 访问a[j+1]越界了，打印几次试试呗
sink + swim 是什么意思？[ema1]求老司机解释解释
【 在 ml3615556 的大作中提到: 】
: 数组下标从0开始，到length - 1结束
: 堆排序建议还是写sink + swim，野路子自己写写就好。。
sink与swim都是为了保持堆有序的算法，顾名思义，一个上浮一个下沉
http://m.blog.csdn.net/article/details?id=47058121
【 在 ywq956283501 的大作中提到: 】
: sink + swim 是什么意思？求老司机解释解释
建议你调试一下，这样能够更清楚的知道问题出在哪，也能知道你这么写的思想。而且，你发现没，你对数组的排序都是从下标为1开始的，那下标为0的元素不就懵逼了。
public static void main(String[] args) {
int[] a = {10,50,30,20,60,80,70,90,40};
buildHeap(a);
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
public static void buildHeap(int[] a) {
for(int i = a.length / 2; i >= 0; i--)
percDown(a, i, a.length);
for(int i = a.length - 1; i > 0; i--) {
swap(a, 0, i);
percDown(a, 0, i);
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private static void percDown(int[] a, int i, int n) {
int child,tmp;
for(tmp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if(child != n - 1 && a[child] < a[child + 1])
child++;
if(tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
private static int leftChild(int i) {
return 2 * i + 1;
}
【 在 ywq956283501 的大作中提到: 】
: package com.package5;
: public class HeapSort {
: public static void main(String[] args) {
: ...................