Java 堆排序实例(大顶堆、小顶堆)

Java 堆排序实例（大顶堆、小顶堆） 在计算机科学中，堆排序是一种基于堆这种数据结构的排序算法。堆是一种近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的平均时间复杂度为Ο(nlogn) 。 堆排序的思想是利用大顶堆（小顶堆）堆顶记录的是最大关键字（最小关键字）这一特性，使得每次从无序中选择最大记录（最小记录）变得简单。其基本思想为：将初始待排序关键字序列（R1,R2….Rn）构建成大顶堆，此堆为初始的无序区；然后，将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区（R1,R2,……Rn-1）和新的有序区（Rn），且满足R[1,2...n-1]<=R[n]；重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 堆排序的重要操作是构造初始堆和调整堆。构造初始堆实际上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。调整堆的过程是从最后一个非叶节点开始调整，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换（交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整）。 堆排序是一种不稳定的排序算法，不适合记录较少的排序。其最坏情况下时间复杂度为nlogn。实际应用中，堆排序可以用来取得一定条件下的最大值或最小值，例如：需要在100个数中找到10个最大值，可以定义一个大小为10的堆，把100中的前十个数据建立成小顶堆（堆顶最小），然后从100个数据中的第11个数据开始与堆顶比较，若堆顶小于当前数据，则把堆顶弹出，把当前数据压入堆顶，然后把数据从堆顶下移到一定位置即可。 在 Java 中，可以使用以下代码来实现堆排序： ```java public class Test0 { public static void heapSort(int[] arr) { // 构造初始堆 buildHeap(arr); // 排序 for (int i = arr.length - 1; i >= 0; i--) { // 将堆顶元素和最后一个元素交换 swap(arr, 0, i); // 调整堆 adjustHeap(arr, 0, i - 1); } } private static void buildHeap(int[] arr) { // 从最后一个非叶节点开始调整 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length - 1); } } private static void adjustHeap(int[] arr, int start, int end) { // 从父节点、左孩子节点、右孩子节点三者中选择最大者 int max = start; int left = 2 * start + 1; int right = 2 * start + 2; if (left <= end && arr[left] > arr[max]) { max = left; } if (right <= end && arr[right] > arr[max]) { max = right; } if (max != start) { swap(arr, start, max); adjustHeap(arr, max, end); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ```