5、堆排序
2021/4/7 10:42:58
本文主要是介绍5、堆排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
5、堆排序(Heep Sort)
-
用数列构建出一个大顶堆,取出堆顶的数字;
-
调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字;
-
循环往复,完成整个排序。
分析:
时间复杂度:
- 最好:O(nlogn)
- 最坏:O(nlogn)
空间复杂度:
- O(1)
不稳定
代码
public static void heapSort(int[] arr) { // 构建初始大顶堆 buildMaxHeap(arr); for (int i = arr.length - 1; i > 0; i--) { // 将最大值放到数组最后 exchange(arr, 0, i); // 调整剩余数组,使其满足大顶堆 maxHeapify(arr, 0, i); } } // 构建初始大顶堆 public static void buildMaxHeap(int[] arr) { // 从最后一个非叶子结点开始调整大顶堆,最后一个非叶子结点的下标就是 arr.length / 2-1 for (int i = arr.length / 2 - 1; i >= 0; i--) { maxHeapify(arr, i, arr.length); } } // 调整大顶堆,第三个参数表示剩余未排序的数字的数量,也就是剩余堆的大小 private static void maxHeapify(int[] arr, int i, int heapSize) { // 左子结点下标 int l = 2 * i + 1; // 右子结点下标 int r = l + 1; // 记录根结点、左子树结点、右子树结点三者中的最大值下标 int largest = i; // 与左子树结点比较 if (l < heapSize && arr[l] > arr[largest]) { largest = l; } // 与右子树结点比较 if (r < heapSize && arr[r] > arr[largest]) { largest = r; } if (largest != i) { // 将最大值交换为根结点 exchange(arr, i, largest); // 再次调整交换数字后的大顶堆 maxHeapify(arr, largest, heapSize); } } // 交换元素 private static void exchange(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
这篇关于5、堆排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?