简单易懂的堆排序 发表于 2018-05-27 | 分类于 基础知识 简单易懂的堆排序网上已经有很多文章都在介绍堆排序的原理,这里记录下比较容易理解的代码思路,通过元素下沉的方式,构建大根堆,以及将首尾元素互换后的调整过程。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354public class HeapSort { public static void main(String []args){ int []arr = {8,9,6,5,10,2,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ //1.构建大顶堆 for(int i=arr.length/2 - 1;i>=0;i--){ //从第一个非叶子结点从下至上,从右至左调整结构 nodeDown(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 nodeDown(arr,0,j);//重新对堆进行调整 } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上),即元素下沉,对于2i+1为左子节点 * 2i+2为右子节点,在子节点中找出最大的一个,并交换,如此一步步下沉到最底部 * @param arr * @param i 需要调整的节点序列 * @param length */ public static void nodeDown(int []arr, int i, int length){ for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始 int temp = arr[i];//先取出当前元素i if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点 k++; } if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) swap(arr, i, k); i = k; }else{ break; } } } /** * 交换元素 * @param arr * @param a * @param b */ public static void swap(int []arr,int a ,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; }}