java堆排序算法实现实例源码。终于明白啥是堆排序了，原来堆只是个幻象，是个虚拟模型，不必要真的弄一棵树出来，直接操作的对象仍然是数组。若要升序排序，则构造大顶堆，每次将堆顶元素删除后放置到堆尾的后一个位置，堆不断缩小。

堆排序源代码实例：

public class Test {
/**
* 堆排序演示程序
*/
public static void main(String[] args) {
int[] a = createArray(20);
System.out.println(Arrays.toString(a));
heapSort(a);
System.out.println(Arrays.toString(a));
}

/**
* 利用堆排序算法，对整型数组进行升序排序
* @param a 整型数组
*/
private static void heapSort(int[] a) {
//最后一个非叶节点的索引为 a.length / 2 – 1
int i, adjust;
//构造大顶堆
for(i=a.length/2-1; i>=0; i–) {
adjust = i;
while((adjust = adjustHeap(a, adjust, a.length))>=0);
}
//将堆顶元素和堆尾元素互换，然后缩小堆的尺寸，再将新堆修正为大顶堆
//重复上述过程，直到堆中还剩1个元素，则排序结束
for(i=a.length-1; i>0; i–) {
adjust = 0;
exchangeValue(a, i, 0);
while((adjust = adjustHeap(a, adjust, i))>=0);
}
}

/**
* 将top为顶的子堆和他的左右两个孩子做一下调整，
* 把最大的元素换到top的位置
* @param a 表示堆的数组
* @param top 待调整的子堆的堆顶
* @return 若返回-1，则表示未做任何调整；反之，返回参与调整的元素的索引
*/
private static int adjustHeap(int[] a, int top, int limit) {
//设某非叶节点索引为 i ，则其左孩子索引为 2 * i + 1，
//右孩子索引为 2 * i + 2;
int result = -1;
int left = 2 * top + 1; //左孩子的索引
int right = left + 1; //右孩子的索引
int maxIndex = -1; //左、右孩子中，拥有最大值的孩子的索引

if(left < limit) { //如果有左孩子
maxIndex = left; //先假设左孩子的值大于右孩子
if(right<limit && a[right] > a[left]) { //如果右孩子的值大于左孩子
maxIndex = right; //修正一下最大值孩子的索引
}
if(a[maxIndex]>a[top]) { //如果孩子的值大于父亲
exchangeValue(a, top, maxIndex); //则交换孩子和父亲的值
result = maxIndex;
}
}
return result;
}

/**
* 交换数组中两个元素的值
* @param a 数组
* @param i 第一个元素的位置
* @param j 第二个元素的位置
*/
private static void exchangeValue(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

/**
* 生成一个没有重复元素的整型数组
* @param length 数组的长度
* @return 无重复元素的整型数组
*/
private static int[] createArray(int length) {
int[] a = new int[length];
Set<Integer> set = new HashSet<Integer>();
Random rand = new Random();
for(int i=0, x=-1; i<a.length;) {
x = rand.nextInt(length*5);
if(set.add(x) == true) {
a[i++] = x;
}
}
return a;
}
}