堆是一种特殊的树形数据结构，其每一个节点都有一个值，通常提到的堆都是完全二叉树，根节点的值小于（大于）两个子节点的值，同时，根节点的两个子树也分别是一个堆。
堆排序主要包括两个过程：一是构建堆，二是交换堆顶元素和最后一个元素位置。
public class HeapSorted { public static void HeapAdjust(int[] a, int parent, int length) { int temp; int child; int num; for (temp = a[parent]; 2 * parent + 1 <= length; parent = child) { child = 2 * parent + 1; if (child + 1 < length && a[child] < a[child + 1]) child++; //交换,注释部分和下面部分同为交换，注释部分较为好理解 /* if(a[child] > temp){ num = a[parent]; a[parent] = a[child]; a[child] = num; } else break; } } */ if(a[child] > temp) a[parent] = a[child]; else break; } a[parent] = temp; } public static void heapSort(int[] list) { int i; // 循环建立初始堆 for (i = list.length / 2 - 1; i >= 0; i--) { HeapAdjust(list, i, list.length - 1); } // 进行n-1次循环，完成排序 for (i = list.length - 1; i >= 0; i--) { // 最后一个元素和第一元素进行交换 int temp = list[0]; list[0] = list[i]; list[i] = temp; // 去掉最后一个元素对剩下的i-1个结点的调整堆 HeapAdjust(list, 0, i - 1); } } public static void main(String[] args) { int[] num = {2,4,3,5,9,7}; heapSort(num); for (int i = 0; i < num.length; i++) { System.out.PRint(num[i] + " "); } }}新闻热点
疑难解答
