堆排序基础介绍不好，平均时间复杂度为O(nlogn)，属于不稳定排序。堆是一棵完全二叉树，具有以下性质：每个节点的值都大于或等于其左右子节点的值，称为大顶堆。注意：不要求最多子节点的值有大小关系。每个节点的值都小于或等于左右子节点的值，称为小顶堆。大顶堆的特点：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]，i对应节点个数，i从0号开始。小顶堆的特点：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]，i对应节点个数，i从0开始。一般情况下，升序采用大顶堆，降序采用小顶堆。堆排序的基本思想将待排序的序列构造成一个大的顶堆，此时整个序列的最大值就是堆顶的根节点。与数组末尾的元素交换，此时末尾为最大值。然后将剩下的n-1个元素重建成堆，这样就会得到n个元素中倒数第二小的值。如此反复执行，就可以得到一个有序的序列。可以看出，在构建大顶堆的过程中，元素个数逐渐减少，最终得到一个有序序列。数组中非叶节点的个数=arr.length/2-1代码示例packagecom.xie.tree;publicclassHeapSort{publicstaticvoidmain(String[]args){int[]arr=newint[8000000];for(inti=0;i<8000000;i++){arr[i]=(int)(Math.random()*800000000);}longstart=System.currentTimeMillis();heapSort(arr);longend=System.currentTimeMillis();System.out.println("耗时:"+(end-start)+"ms");/***800万数据*堆排序！！*耗时：2482ms*/}publicstaticvoidheapSort(int[]arr){inttemp=0;System.out.println("堆排序！！");//1.将乱序的序列构成一个堆，根据升序和降序要求选择大顶堆或小顶堆为(inti=arr.length/2-1;i>=0;i--){adjustHeap(arr,i,arr.length);}//2。将堆顶元素与数组尾元素交换，将最大的元素“下沉”到数组尾//3。重新调整结构，使其满足堆定义，然后继续将堆顶元素与当前末尾元素进行交换，反复执行调整+交换步骤，直至整个序列有序。for(intj=arr.length-1;j>0;j--){//交换temp=arr[j];arr[j]=arr[0];arr[0]=temp;adjustHeap(arr,0,j);}}/***将一个数组（二叉树）调整为大顶堆*功能：完成将i对应的有非叶子节点的树调整为大顶堆**@paramarr待调整数组*@parami表示非叶子节点在数组中的索引*@paramlength表示调整多少个元素，长度逐渐递减*/publicstaticvoidadjustHeap(int[]arr,inti,intlength){//先获取当前元素的值，存入临时变量inttemp=arr[i];//k=2*i+1为i节点的左子节点for(intk=2*i+1;k
