源码分享站,云推荐 wordpress,深圳常桉网站建设,wordpress三站合一堆排序是一种基于堆这种数据结构的比较排序算法#xff0c;它是一种原地、不稳定的排序算法#xff0c;时间复杂度为 O(n log n)。堆排序的基本思想是将数组构建成一个二叉堆#xff0c;并通过反复调整堆顶和未排序部分之间的关系来实现排序。
堆的定义
堆是一种特殊的完全…堆排序是一种基于堆这种数据结构的比较排序算法它是一种原地、不稳定的排序算法时间复杂度为 O(n log n)。堆排序的基本思想是将数组构建成一个二叉堆并通过反复调整堆顶和未排序部分之间的关系来实现排序。
堆的定义
堆是一种特殊的完全二叉树分为最大堆和最小堆
最大堆每个节点的值都大于或等于其子节点的值堆顶为最大值。最小堆每个节点的值都小于或等于其子节点的值堆顶为最小值。 在堆排序中通常使用最大堆来进行升序排序。
完全二叉树
堆结构基于完全二叉树所有层的节点均填满且最下层的节点靠左排列通过数组来表示堆每个节点的索引关系为
父节点(i - 1) / 2左子节点2 * i 1右子节点2 * i 2
堆排序的原理
堆排序基于最大堆的特性
最大堆的堆顶是整个数组的最大值。通过构建最大堆将最大值与数组的末尾元素交换此时堆的大小减少1排除掉已排好的最大值。调整剩余的堆使其继续满足最大堆的性质重复上述过程最终得到有序数组。
堆排序的步骤
堆排序分为两个阶段
构建最大堆 从最后一个非叶子节点开始向上调整每个子树使其满足最大堆的性质。排序 将堆顶元素与堆的最后一个元素交换然后对剩余的元素继续调整为最大堆。每次将最大值放在数组的末尾。
Java代码实现 public class HeapSort {// 主函数堆排序算法public void heapSort(int[] arr) {int n arr.length;// 1. 构建最大堆for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}// 2. 一个个将最大值交换到末尾并调整堆for (int i n - 1; i 0; i--) {// 将堆顶元素和末尾元素交换swap(arr, 0, i);// 调整堆去掉已排序的元素heapify(arr, i, 0);}}// 调整堆的函数确保以root为根的子树满足最大堆性质private void heapify(int[] arr, int n, int root) {int largest root;int left 2 * root 1; // 左子节点int right 2 * root 2; // 右子节点// 如果左子节点比root节点大if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点比当前largest节点大if (right n arr[right] arr[largest]) {largest right;}// 如果largest不是root交换root和largestif (largest ! root) {swap(arr, root, largest);// 递归地对受影响的子树进行堆调整heapify(arr, n, largest);}}// 辅助函数交换数组中的两个元素private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}// 打印数组函数public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i );}System.out.println();}// 测试堆排序public static void main(String[] args) {int[] arr {12, 11, 13, 5, 6, 7};HeapSort heapSort new HeapSort();System.out.println(原始数组:);printArray(arr);heapSort.heapSort(arr);System.out.println(排序后的数组:);printArray(arr);}
}
输出结果
原始数组:
12 11 13 5 6 7
排序后的数组:
5 6 7 11 12 13
堆排序的时间和空间复杂度
时间复杂度 构建最大堆O(n)。 调整堆每次调整堆的时间复杂度为 O(log n)共进行 n 次调整。因此堆排序的总体时间复杂度为 O(n log n)。
空间复杂度 堆排序是原地排序算法不需要额外的存储空间空间复杂度为 O(1)。
堆排序的优缺点
优点
时间复杂度稳定堆排序的时间复杂度始终为 O(n log n)无论是最好、最坏还是平均情况。空间复杂度低堆排序是原地排序算法空间复杂度为 O(1)非常节省内存。不依赖于输入数据的分布堆排序对输入数据的初始状态不敏感始终保证 O(n log n) 的时间复杂度。
缺点
不稳定堆排序可能改变相同元素的相对顺序因此它不是一个稳定的排序算法。常数因子较高堆排序在实际应用中的速度通常比快速排序稍慢这是因为堆排序中的堆调整操作较复杂。
使用场景
需要稳定时间复杂度的场合在无法预知输入数据分布或输入数据最坏情况下其他算法如快速排序性能下降时堆排序是一种保证 O(n log n) 时间复杂度的选择。内存受限场景堆排序的空间复杂度为 O(1)因此在内存紧张的场景下非常有用。优先队列的实现堆结构常用于实现优先队列等数据结构。
总结
堆排序是一种稳定高效的排序算法时间复杂度为 O(n log n)空间复杂度为 O(1)具有普遍适用的特点。虽然其不稳定性和相对较高的常数因子可能在某些应用中影响其表现但在需要稳定时间复杂度和低内存消耗的场合下堆排序仍然是一个理想的选择。
