堆排序

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

public class HeapSort { /** * 构造大顶堆 * 1. 根节点的值一定要比子节点的值大 * 堆的向下调整 * @param array 需要调整的数组 * @param start 调整的起始位置 * @param end 调整的终止位置 * 索引从0开始 * 当前节点的左节点： 2*i+1 * 右节点： 2**i+2 */ public static void max_heap_down(int[] array,int start,int end){ int currentIndex=start; //保存当前节点的下标 int leftIndex=2*currentIndex+1; //当前节点左节点的下标 //当当前节点的左节点的下标小于终止下标的时候，因为堆是一个完全的二叉树，因此只要没有左子树就一定没有右子树，因此只需要判断左节点的下标即可 //只要满足这个条件就表示一定存在左右节点 while(leftIndex<end){ //当左节点的值小于右节点，那么此时只需要将当前值和右节点的值比较，这里的leftIndex+1是右子节点的下标 //如果没有执行if体内的语句，那么此时的左右节点最大的下标就是左节点的下标 if(array[leftIndex]<array[leftIndex+1]){ leftIndex++; //此时的下标编程右节点的下标 } //如果当前节点大于等于左右子节点中的最大值，那么就不用调整了，直接跳出 if (array[currentIndex]>=array[leftIndex]) { break; }else { //如果小于，此时需要调整，将当前节点和左右子节点最大值交换 int temp=array[currentIndex]; //交换数字 array[currentIndex]=array[leftIndex]; array[leftIndex]=temp; currentIndex=leftIndex; //此时的当前节点的下标 leftIndex=2*currentIndex+1; //当前节点的左子节点也需要改变了 } } } /** * 堆排序，从小到大 * @param array 待排序的数组 */ public static void heap_sort_asc(int[] array){ //从索引为array.length/2-1的位置到0，开始向下调整，那么调整好的数组就是一个大顶堆 for(int i=array.length/2-1;i>=0;i--){ //进行向下调整 max_heap_down(array, i, array.length-1); } //从最后一个元素开始对序列进行调整，不断的调整，直到第一个元素 for (int i = array.length-1; i >0; i--) { //此时array[0]就是最大的元素，因此和最后一个元素交换 int temp=array[i]; array[i]=array[0]; array[0]=temp; //此时最后一个元素就是最大的，因此我们对前面的元素继续构造大顶堆 max_heap_down(array, 0, i-1); } } public static void main(String[] args) { int[] array={12,3,4,45,1,45,6,72,4}; heap_sort_asc(array); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } }}