Java实现堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序是一种选择排序，他的最好、最坏，平均时间复杂度均为O(nlogn)，它也是不稳定的排序。

堆是具有以下性质的完全二叉树：

（1）每个结点的值都大于或等于其左右子结点的值，称为大顶堆 （2）每个结点的值都小于或等于其左右子结点的值，称为小顶堆 （3）升序使用大顶堆，降序使用小顶堆

堆排序的思路：

（1）将需要排序的序列构成一个大(小)顶堆 （2）整个序列的最大、最小值就是堆顶的根结点 （3）将其与末尾元素交换，此时末尾就位最大值 （4）将剩余n-1个元素重新构造成一个堆，这样将会得到n个元素的次大(小)值。 （5）重复步骤，就可以得到有序序列了

堆排序图解：

实现代码：

package com.struct; import java.security.PublicKey; import java.util.Arrays; public class HeadSort { public static void main(String[] args) { int[] arr = {4,6,8,5,9}; headSort(arr); } //编写一个堆排序的方法 public static void headSort(int[] arr) { //定义一个临时变量 int temp; for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHead(arr,i,arr.length); } for (int j = arr.length-1; j > 0 ; j--) { //将顶堆元素与末尾元素交换，将最大值放入数组末端 temp = arr[j]; arr[j] = arr[0];//此时arr[0]为最大值 arr[0] = temp; adjustHead(arr,0,j); } System.out.println(Arrays.toString(arr)); } /*！局部！将一个二叉树(数组)调整成一颗大顶堆二叉树 将以i对应的非叶子结点的树调整成大顶堆 arr是待调整的数组， i表示非叶子结点在数组中的索引， length表示对多少个元素进行调整 */ public static void adjustHead(int[] arr,int i,int length) { int temp = arr[i];//取出当前元素的值，存放在一个临时变量 //k是i结点的左子结点 for (int k =2*i+1; k < length; k++) { if (arr[k] < arr[k+1] && (k+1) < length)//此时左子结点小于右子结点，交换 k++;//指向右子结点 if (arr[k] > temp)//此时子结点大于父结点 { arr[i] = arr[k];//将大的值赋给当前结点 i = k;//i指向k，继续比较 } else { break; } arr[i] = temp;//将temp放到调整后最后边 } } }