Java 算法分析 堆排序

package duipaixu; import java.util.Random; /**
 * 2020/8/8
 * 16:27
 */ public class HeapSort { public static void main(String[] args) { //int[] arrays={4,6,8,5,9}; int[] arrays=new int[99999]; for(int i=0;i<99999;i++){ arrays[i]=new Random().nextInt(99999); } long start=System.currentTimeMillis(); Sort(arrays); long end=System.currentTimeMillis(); System.out.println(end-start); //System.out.println(Arrays.toString(arrays)); } public static void Sort(int[]arrays){ //数组的长度 int len=arrays.length; for(;len>0;len--){ //最后一个非叶子节点 int end=(len-1)/2; //向上进行调整堆（一次） for(int i=end;i>=0;i--){ heapSort(arrays,i,len); } //把最大的值和数组最后的值进行交换 int temp=arrays[0]; arrays[0]=arrays[len-1]; arrays[len-1]=temp; } } /**
     *
     * @param arrays 数组
     * @param end 非叶子节点
     * @param len 数组长度
     */ public static void heapSort(int[] arrays,int end,int len){ //存储非叶子节点的值 int temp=arrays[end]; //找到非叶子节点的孩子节点进行比较，并向下进行调整。 for(int i=end*2+1;i<len;){ if(i+1<len&&arrays[i]<arrays[i+1]){ i++; } if(arrays[i]>temp){ arrays[end]=arrays[i]; //交换完调整下面的堆 end=i; //再往下判断 i=i*2+1; }else{ break; } } //把非叶子节点的值给最终的位置 arrays[end]=temp; } }

20993

本文地址：https://blog.csdn.net/m0_45196258/article/details/107884936