1 思路
总体思路
首先我们会拿到一个无序的数组,我们需要先对其构建成一个堆。下面我们示例将会构建成大顶堆。然后我们对顶堆的元素进行位置之间的交换。交换的同时继续对其维护大顶堆的性质,直至大顶堆只剩下一个元素。
具体思路
首先我们先将一个无序数据将其构建成一个大顶堆。我们将数据模拟成一个大顶堆,并不是真实地去构建。其实就是按照堆中元素下标对应关系来实现。
元素之间下标关系:
下标为 i 的节点的父节点下标为 (i + 1) / 2
下标为 i 的节点的左孩子的下标为 i * 2 + 1
下标为 i 的节点的右孩子的下标为 i * 2 + 2
然后我们来调整这个数组让他符合大顶堆的规则,就是调整对应的下标,交换数组内的元素
然后我们把整个数组看成未排序和已排序两个部分,也就是未排序的数组的最大的元素和最小的元素的位置。在交换之后最大的元素已经在数组最后面,此时最后面就是有序的数组。然后我们在维护这个顶堆的规则。
2 具体实现
import java.util.*;public class Main {// 主函数入口public static void main(String[] args) {// 初始化一个整型数组int arr[] = new int[]{2, 1, 8, 122, 3, 6, 10, 11};// 调用sort方法对数组进行排序sort(arr);// 遍历排序后的数组并打印每个元素for (int i : arr) {System.out.print("" + i + " ");}}// 排序方法,使用堆排序算法static void sort(int arr[]) {int n = arr.length; // 获取数组长度// 从最后一个非叶子节点开始,向下调整每个节点,构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heap_sort(arr, n, i);}// 从最后一个元素开始,将其与堆顶元素交换,然后对堆进行调整for (int i = n - 1; i > 0; i--) {swap(i, 0, arr); // 将当前元素与堆顶元素交换heap_sort(arr, i, 0); // 对堆进行调整}}// 堆排序的辅助方法,用于向下调整堆private static void heap_sort(int[] arr, int n, int i) {int largest = i; // 初始化最大元素索引为当前节点int lson = i * 2 + 1; // 左子节点索引int rson = i * 2 + 2; // 右子节点索引// 如果左子节点存在且值大于当前最大元素,则更新最大元素索引if (lson < n && arr[lson] > arr[largest]) {largest = lson;}// 如果右子节点存在且值大于当前最大元素,则更新最大元素索引if (rson < n && arr[rson] > arr[largest]) {largest = rson;}// 如果最大元素不是当前节点,则交换它们,并递归地调整堆if (largest != i) {swap(largest, i, arr);heap_sort(arr, n, largest);}}// 交换数组中的两个元素private static void swap(int maxIndex, int minIndex, int arr[]) {int temp = arr[maxIndex]; // 临时变量用于交换arr[maxIndex] = arr[minIndex];arr[minIndex] = temp;}
}
3 总结
- 堆排序使用堆来选数,效率就高了很多。
- 时间复杂度:O(N*logN)
- 空间复杂度:O(1)
- 稳定性:不稳定