详解Java常用排序算法-堆排序

堆排序算法详解 堆排序是一种树形选择排序算法，它的基本思想是将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为 O(nlogn)。 堆的概念： 堆是一种特殊的树形数据结构，它满足以下两个性质： 1. 堆中某个节点的值总是不大于或不小于其父节点的值。 2. 堆总是一棵完全二叉树。 在堆排序算法中，我们使用大根堆或小根堆来存储待排序的数组。其中，大根堆的根节点是最大值，小根堆的根节点是最小值。 堆排序算法的步骤： 1. 构建大根堆：首先将待排序的数组构建成一个大根堆。这是通过 heapify 函数来实现的，该函数将数组中的每个节点与其左右子节点进行比较，确保父节点的值总是不小于其左右子节点的值。 2. 依次取出堆顶元素：然后，我们依次取出堆顶元素，并将其与堆底元素交换位置。 3. 重构堆：在取出堆顶元素后，我们需要将剩余元素重新构建成堆，以便继续执行排序操作。 Java 实现： 在上面的代码中，我们使用 Java 语言实现了堆排序算法。其中，Heap 类中包括两个函数：heapSort 和 heapify。heapSort 函数接受一个整数数组作为输入，并使用堆排序算法对该数组进行排序。heapify 函数用于对一个节点进行堆化操作。 heapSort 函数的实现： public static void heapSort(int[] arr) { int n = arr.length; // 构建大根堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 依次取出堆顶元素，并将余下元素继续堆化，得到有序序列 for (int i = n - 1; i >= 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } heapify 函数的实现： private static void heapify(int[] arr, int heapSize, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // 找到左右子节点中的最大值 if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点，则交换根节点与最大值节点，并递归地对最大值节点进行堆化 if (largest != i) { swap(arr, i, largest); heapify(arr, heapSize, largest); } } 时间复杂度： 堆排序算法的时间复杂度为 O(nlogn)，其中 n 是待排序的数组的大小。这是因为在构建大根堆时，我们需要执行 n/2-1 次堆化操作，每次操作的时间复杂度为 O(logn)，因此总的时间复杂度为 O(n/2-1 \* logn) = O(nlogn)。