堆排序算法，基于选择排序的思想，利用堆结构的性质来完成对数据的排序。
前提准备：
-
什么是堆结构：
堆数据结构是一种数组对象，它可以被视为一科完全二叉树结构。它的特点是父结点的值大于（小于）两个子结点的值（分别称为大顶堆和小顶堆）
堆示意图 堆结构的性质：
对于第n个结点而言 --- 它的父结点下标 i = （n-1）/ 2，左子结点 left = 2n+1，右子结点 right =2n+2
结构图
算法基本思想：
1. 构建堆（大顶堆或小顶堆，现以大顶堆为例）：
- 首先从最后一个结点开始，找到它的父结点，在父结点和父结点的左右结点中，选出最大的值，与父节点交换。
- 然后对倒数第二个结点执行同样的操作
- 这样直到根结点的时候，根结点变成了所以数据中最大的值。
2. 替换根结点，重建堆：
- 将根结点与最后一个结点的数据交换，在把倒数第二个结点视为最后一个结点，重新建堆。
- 重复上述的操作。最终，数据排序完成。
代码实现：
import java.util.Arrays;
/**
* Created by noonbiteun
* Date: 2017/7/31
*/
public class HeapSort {
//建堆
private static void heapConstruct(int[] arr, int last) {
int tmp;
for (int parent = (last - 1) / 2; parent >= 0; parent = (last-1) / 2) {
if (2*parent+1 < last) {
//第last个节点为右子树
if (arr[last - 1] < arr[last]) {
//大的数据往前移
tmp = arr[last];
arr[last] = arr[last - 1];
arr[last - 1] = tmp;
} else {
last--;
}
}
if (arr[parent] < arr[last]) {
//大的数据移到父节点
tmp = arr[last];
arr[last] = arr[parent];
arr[parent] = tmp;
}
last--;
}
}
private static void sort(int[] arr) {
int last = arr.length - 1;
int tmp;
System.out.println("原始顺序： " + Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
heapConstruct(arr, last);
//第一个和最后一个交换
tmp = arr[0];
arr[0] = arr[last];
arr[last] = tmp;
last--;
System.out.println("第" + i + "趟排序：" + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = new int[10];
//初始化数组
for (int i = 0; i < 10; i++) {
arr[i] = (int) (Math.random() * (100 + 1));
}
HeapSort.sort(arr);
}
}
输出结果：
运行结果
小结分析：
经过两三天的不断学习，感觉这方面在一点点的进步，今天的这个堆排序，只看了书上写的算法思想之后，马上就能写出来，感觉比前几天对着一个冒泡排序死磕了一个小时要进步很大了，加油。
