堆排序之Java实现
代码：
package cn.com.zfc.lesson21.sort; /**
*
* @title HeapSort
* @describe 堆排序
* @author 张富昌
* @date 2016年10月2日下午5:33:50
*/
public class HeapSort {
public static void main(String[] args) {
// 声明整型数组
int[] array = new int[10];
// 使用循环和随机数初始化数组
for (int i = 0; i < array.length; i++) {
array[i] = (int) Math.round(Math.random() * 100);
}
System.out.println("原始数组为：");
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("排序后的数组为：");
for (int i : heapSort(array)) {
System.out.print(i + " ");
}
} /**
*
* 功能：堆排序的基本思想是
*
* 参数：int[] array
*
* 返回类型：int[]
*/
public static int[] heapSort(int[] array) {
int[] arr = array;
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
// 将 0~[n-1]调整成大顶堆
heapAdjust(arr, i, arr.length - 1);
}
for (int i = arr.length - 1; i > 0; i--) {
// 第 i 趟排序
swap(arr, 0, i);
heapAdjust(arr, 0, i - 1);
} return arr;
} /**
*
* 功能：将待排数组调节成大顶堆，调整 arr[low]，使除它以外的元素成为大顶堆
*
* 参数：int[] arr, int low, int high
*
* 返回类型：void
*/
public static void heapAdjust(int[] arr, int low, int high) {
for (int f = low, i = 2 * low + 1; i <= high; i = 2 * i + 1) {
// f 为被调整的结点，i 为 f 的最大孩子
if (i < high && arr[i] < arr[i + 1]) {
// 右孩子更大，则 i 指向右孩子
i++;
}
if (arr[f] >= arr[i]) {
// 已经成为大顶堆了
break;
}
// 交换调整结点的位置
swap(arr, f, i);
// 让 i 成为新的调整结点
f = i;
}
} /**
*
* 功能：交换两个数的值
*
* 参数：int i, int j
*
* 返回类型：void
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp; }
}
运行结果：