java堆排序.docxVIP

package ds;import java.util.*;public class HeapSort {int[] num;int length;//数组长度public void accept(){Scanner sc=new Scanner(System.in);System.out.println(请输入数组长度);length=sc.nextInt();num=new int[length];for(int i=0;ilength;i++){System.out.println(请输入数);num[i]=sc.nextInt();}}//将二叉树转换为堆,n代表的是元素的个数public void treeToHeap(int n){//i代表的是父节点，首先初始化为最后一个父节点的索引int i=(n-1)/2;//j代表的是左子节点int j=0;//如果父节点没有比较完while(i=0){//如果没有左子节点if(2*i+1=n){i=i-1;//continue;}//如果该父节点有子节点else{ j=2*i+1; //如果有右子节点 if(j+1n) { //比较j和兄弟的大小 if(num[j]num[j+1]) { j=j+1; } } //如果兄弟节点的较大值大于父节点 if(num[j]num[i]) { //交换节点值 int temp=num[j]; num[j]=num[i]; num[i]=temp; } i=i-1;}}}//实现堆排序public void sort(){//last代表最后一个节点int last=length-1;while(last0){//将第一个元素到最后一个元素转换成堆this.treeToHeap(last+1);//将根元素交换到last位置的元素上int temp=num[0];num[0]=num[last];num[last]=temp;last=last-1;}}//排序后遍历public void display(){for(int i:num){System.out.println(i);}}public static void main(String[] args) {HeapSort h=new HeapSort();h.accept();h.sort();h.display();}}重庆NIIT