时间:2021-05-19
复制代码 代码如下:
import java.util.Arrays;
public class HeapSort {
public static void heapSort(DataWraper[] data){
System.out.println("开始排序");
int arrayLength=data.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(data,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(data,0,arrayLength-1-i);
System.out.println(Arrays.toString(data));
}
}
private static void swap(DataWraper[] data, int i, int j) {
// TODO Auto-generated method stub
DataWraper tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
//对data数组从0到lastIndex建大顶堆
private static void buildMaxHeap(DataWraper[] data, int lastIndex) {
// TODO Auto-generated method stub
//从lastIndex处节点(最后一个节点)的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex].compareTo(data[biggerIndex+1])<0){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k].compareTo(data[biggerIndex])<0){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
DataWraper [] data={
new DataWraper(21, ""),
new DataWraper(30, ""),
new DataWraper(49, ""),
new DataWraper(30, "*"),
new DataWraper(16, ""),
new DataWraper(9, ""),
};
System.out.println("排序之前:\n"+Arrays.toString(data));
heapSort(data);
System.out.println("排序之后:\n"+Arrays.toString(data));
}
}
结果:
排序之前:
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 21, 30*, 16, 49]
[16, 30*, 21, 9, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
排序之后:
[9, 16, 21, 30*, 30, 49]
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完
本文实例为大家分享了C#实现堆排序的具体代码,供大家参考,具体内容如下代码://////堆排序方法。/////////待排序数组。///privatevoidH
本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序。实例代码如下:voidFindMaxInHeap(intarr[],const
java实现计数排序和桶排序实例代码目录比较和非比较的区别常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们
本文实例讲述了PHP排序算法之堆排序(HeapSort)。分享给大家供大家参考,具体如下:算法引进:在这里我直接引用《大话数据结构》里面的开头:在前面讲到简单选