最近有好几篇博客都写了一半没写完，今天先贴个简单的堆排序算法吧。
很久以前用PHP和儿童编程语言scratch写过堆排序，今天想试试自己还能不能想起来，就用java又实现了一遍，还是花了挺长时间回忆，
没办法，智商有限。
核心要点（以最大堆为例）：
- 外层一个循环，从数组长度开始递减，这是为了完成一次"建堆-首尾交换"后，有效数组长度（注意不是数组实际长度，实际长度没有变）减1，继续以上过程
- 循环里面分两步，第一步建立最大堆，最大的数就会跑到堆顶，第二步把堆顶这个数放到末尾（和最后一元素交换）就不用管了， 剩下的元素重复以上过程，每重复一次就把次大的数挑出来放到末尾。
- 建堆时首先找到最后一个非叶子结点，完全二叉树的最后一个非叶子结点就是 n/2向下取整，n是数组长度，注意实际元素下标可能要再减1，如果你的数组定义是从零开始的话。
- 建堆就是从最后一个非叶子节点开始倒着往前循环。
- 每循环到一个节点，就从这个节点以及它的两个孩子里面找出最大的那个，如果最大数在孩子里面，就得跟这个节点的数交换，否则就不用管了， 比较前记得判断一下右孩子有没有，或者说是否有效（2i<len）。
- 根据完全二叉树性质，一个分支节点的两个子节点为 2i 和 2i+1，因为数组是从0开始的，所以我代码里是 2i-1 和 2i
import java.util.Arrays;
public class Heapsort {
private static Integer[] arr = {3, 5, 12, 1, 4, 8, 6, 13, 2, 7};
public static void main(String[] args)
{
heapSort();
System.out.println(Arrays.toString(arr));
}
public static void heapSort()
{
int i;
for (i = arr.length; i > 1; i--) {
heapAdjust(i);
swap(0, i-1);
}
}
public static void swap(int a, int b)
{
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
public static void heapAdjust(int len)
{
System.out.println("len="+len);
for (int i = (int) Math.floor(len/2); i >= 1; i--) {
int a = arr[i-1];
System.out.println("a="+a);
int cl = arr[2*i-1];
System.out.println("cl="+cl);
int maxi;
if (2*i < len) {
int cr = arr[2 * i];
System.out.println("cr="+cr);
maxi = cl > cr ? 2 * i - 1 : 2 * i;
} else {
maxi = 2*i-1;
}
if (a < arr[maxi]) {
System.out.println("swap " + (i-1) + " " + maxi);
swap(i-1, maxi);
}
}
System.out.println(Arrays.toString(arr));
System.out.println("\n");
}
}