新人求助:关于堆排序的问题(Java)? 400 报错
新人求助:关于堆排序的问题(Java)? 400 报错
请问下面这个堆排序算法的逻辑哪个部分出错了,部分参考了<<数据结构与算法分析>>(c语言描述),调试了很久还是没能得出正确的排序,麻烦有时间的朋友帮我看看,感激不尽:)
public class MyHeapSort {
/*筛选
* data:待排数组
* k: 需要调整的节点
* heapSize:数组大小
*/
static void heapOne(int[] data, int k, int heapSize){
int parent = k;
int leftChild = 2 * parent +1;
int minChild;
//将需要调整的节点暂存起来
int temp = data[k];
while(leftChild < heapSize){
minChild = leftChild;
//选出最小子节点
if((leftChild != (heapSize -1)) && data[leftChild+1] < data[leftChild])
minChild ++;
//交换
if(data[parent] > data[minChild]){
data[parent] = data[minChild];
parent = minChild;
leftChild = 2 * parent +1;
}else{
break;
}
}
data[parent] = temp;
}
static void heapSort(int[] data){
//建立堆
int n = data.length;
for(int i = data.length / 2 -1 ; i >= 0; i--)
heapOne(data, i, n);
while(n>0){
System.out.print(data[0] + " "); // 输出堆顶元素
data[0] = data[n-1]; // 最后一个元素移动到堆顶
n--;
heapOne(data,0,n);
}
}
public static void main(String[] args) {
int[] a = {1,2,7,6,3,98,5,4};
heapSort(a);
}
}
展开
收起
1
条回答
写回答
写回答
-
https://developer.aliyun.com/profile/5yerqm5bn5yqg?spm=a2c6h.12873639.0.0.6eae304abcjaIBpublic static void swap(int[] data,int i,int j){ int temp = data[i]; data[i] = data[j]; data[j] = temp; } static void heapOne(int[] data, int k, int heapSize){ int parent = k; int leftChild = 2 * parent +1; int minChild; while(leftChild <= heapSize){ minChild = leftChild; //选出最小子节点 if(leftChild <heapSize) if(data[minChild+1] < data[minChild]) minChild ++; //交换 if(data[parent] > data[minChild]){ swap(data,parent,minChild); parent = minChild; leftChild = 2 * parent +1; }else{ break; } } } static void heapSort(int[] data){ //建立堆 int n = data.length-1; while(n>0){ for(int i = (n-1) / 2 ; i >= 0; i--){ heapOne(data, i, n); } swap(data,0,n); n--; }}
根据你的思路改的。
######
引用来自“分流砥柱”的评论
public static void swap(int[] data,int i,int j){ int temp = data[i]; data[i] = data[j]; data[j] = temp; } static void heapOne(int[] data, int k, int heapSize){ int parent = k; int leftChild = 2 * parent +1; int minChild; while(leftChild <= heapSize){ minChild = leftChild; //选出最小子节点 if(leftChild <heapSize) if(data[minChild+1] < data[minChild]) minChild ++; //交换 if(data[parent] > data[minChild]){ swap(data,parent,minChild); parent = minChild; leftChild = 2 * parent +1; }else{ break; } } } static void heapSort(int[] data){ //建立堆 int n = data.length-1; while(n>0){ for(int i = (n-1) / 2 ; i >= 0; i--){ heapOne(data, i, n); } swap(data,0,n); n--; }}
根据你的思路改的。
非常感谢你，根据你给出的修改方案，我找到了原来程序的问题所在，原来只需要将：
//交换
if(data[parent] > data[minChild]){
data[parent] = data[minChild];
parent = minChild;
leftChild = 2 * parent +1;
}
——————————————————————
data[parent] > data[minChild] 改为：temp > data[minChild]即可。
其中，temp 存储了最原先那个需要调整的节点的值。
原来程序不采用swap()的原因是可以尽可能减少交换的次数，通过下标的移动确定出最后需要交换的两个节点，这样就只需要交换一次即可达到目的。
Thank you ：）2020-06-01 10:51:14赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
