一、什么是堆排序
堆排序是将数组看做一个完全二叉树(附录里有二叉树的解释)，具有以下的性质：
1）每个节点的值都大于子节点的值，叫做大顶堆。
大顶堆
2）每个节点的值都小于子节点的值，叫做小顶堆。
小顶堆
二、堆排序的实现原理
大顶堆是将数组按照升序的方式进行排序。原理是：
（1）从最后一个根节点开始，比较父节点和两个子节点的值，如果子节点的值大于父节点，则交换两点的数值，否则不交换。
（2）从最后一个根节点依次比较到顶点 ，也就是上图0节点的位置。这样进行一轮比较之后，得到的0节点的数值就是该数组中最大的数值。
（3）再将0节点的数值与该数组最后一个子节点的数值进行交换。这是最后一个子节点位置上的值便是该数组中最大的值。
（4）这时，把数组的倒数第二个子节点当做数组的结尾，再次将0节点作为父节点进行大顶堆操作，这样重复到数组的结尾为1节点，数组排序完成。
（5）将数组输出可以看到该数组变为一个升序的数组。
小顶堆则与大顶堆正好相反。
三、代码实现：
package JavaDay_13
publc class Heapsort {
public static void main(String[] args) {
int[] arr = {1,5,6,8,7,2,3,4,9,4,15,12}; //创建一个数组
heapSort(arr); //调用heapSort方法进行第一次排序，选出最大值放在0节点
for(int i=0;i<arr.length;i++){ //将arr数组输出
System.out.print(arr[i]+" ");
}
}
public static void heapSort(int[]arr){
int n= arr.length-1;
for(int i=n/2-1;i>=0;i++){ //从最后一个根节点开始，直到0节点位置
heapAdjust(arr,i,n); // 传入参数arr数组，父节点 i ，数组长度n
}
for(int i=n;i>0;i--) { //从最后一个节点开始，到取到倒数第二个节点
swap(arr,i); //调用方法，将此时的 i 与arr数组的第一个值交换
heapAdjust(arr,0,i-1); //再次构建大顶堆
}
}
public static void heapAdjust(int[] arr,int parent,int length) {
int temp = arr[parent]; //设置一个初始值记录arr[parent]的数值
for(int i=parent*2+1;i<=length;i=i*2+1) {
// i为父节点的左节点，每次循环结束后，i节点成为父节点，i迭代为自己之前的数的左节点
if(i<length && arr[i]<arr[i+1]){
i++; //如果i的左节点小于右节点，则i+1变为右节点
}
if(temp>arr[i]) {
break; // 如果左右节点中较大的值小于父节点，则跳出
}
arr[parent] = arr[i]; //让父节点的值变为i节点的值
parent = i; //此时父节点变为i；
}
arr[parent] = temp; // 将刚刚得到的父节点赋值给新位置
}
public static void swap(int[] arr,int i) { //将数组arr中的i的值与0交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
}
附录：
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
网友评论