可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后得到一个有序序列了
一个数组中非叶子节点的个数 = arr.length / 2 - 1
- package com.xie.tree;
- public class HeapSort {
- public static void main(String[] args) {
- int[] arr = new int[8000000];
- for (int i = 0; i < 8000000; i++) {
- arr[i] = (int) (Math.random() * 800000000);
- }
- long start = System.currentTimeMillis();
- heapSort(arr);
- long end = System.currentTimeMillis();
- System.out.println("耗时:" + (end - start) + "ms");
- /**
- * 800万数据
- * 堆排序!!
- * 耗时:2482ms
- */
- }
- public static void heapSort(int[] arr) {
- int temp = 0;
- System.out.println("堆排序!!");
- //1.将无序序列构成一个堆,根据升序降序需求选择大顶堆或小顶堆
- for (int i = arr.length / 2 - 1; i >= 0; i--) {
- adjustHeap(arr, i, arr.length);
- }
- //2.将堆顶元素与数组末尾元素交换,将最大元素"沉"到数组末端
- //3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
- for (int j = arr.length - 1; j > 0; j--) {
- //交换
- temp = arr[j];
- arr[j] = arr[0];
- arr[0] = temp;
- adjustHeap(arr, 0, j);
- }
- }
- /**
- * 将一个数组(二叉树),调整成一个大顶堆
- * 功能:完成将以 i 对应的非叶子节点的树调整成大顶堆
- *
- * @param arr 待调整的数组
- * @param i 表示非叶子节点在数组的索引
- * @param length 表示对多少个元素进行调整,length在逐渐减少
- */
- public static void adjustHeap(int[] arr, int i, int length) {
- //先取出当前元素的值,保存在临时变量
- int temp = arr[i];
- //k = 2 * i + 1 是i节点的左子节点
- for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
- //当左子节点值小于右子节点值
- if (k + 1 < length && arr[k] < arr[k + 1]) {
- k++;//k指向右子节点
- }
- //如果子节点值大于父节点值
- if (arr[k] > temp) {
- //把较大的值赋给当前节点
- arr[i] = arr[k];
- //!!! i指向k 继续循环比较
- i = k;
- } else {
- break;
- }
- }
- //当for循环结束后,我们已经将以 i 为父节点的树的最大值,放在了最顶。
- //将temp值放到调整后的位置
- arr[i] = temp;
- }
- }
1. 背景 Proxy服务负责消费CKafka消息并解析,并分发消息至不同的CKafka topic。...
就地过年,谁在助力大城小村的有序运行,谁来慰藉远方游子的一抹乡愁?除了各行各...
什么是元数据(metadata) 元数据由metadata译来,所谓的元数据就是关于数据的数据...
本文转载自微信公众号「后端Q」,作者conan。转载本文请联系后端Q公众号。 概述 ...
本文转载自公众号读芯术(ID:AI_Discovery)。 笔者认为,编程最难的部分之一,并...
在本文中我将把自己最常用的 jQuery 函数转换为原生 JavaScript。 有时我需要创...
随着人工智能技术的兴起以及边缘设备算力的提升,机器视觉的应用场景不断扩展,...
H5页面适配及微信默认字号问题的最佳实践 Write By CS逍遥剑仙 我的主页: csxiao...
本文转载自微信公众号「bugstack虫洞栈」,作者小傅哥。转载本文请联系bugstack...
前言 语言的内存管理是语言设计的一个重要方面。它是决定语言性能的重要因素。无...