RuiCode

  • 首页
  • 归档

  • 搜索
操作系统 并发 排序 网络 源码分析 二分法 面试 不重复算法 指针移动 java 算法 mysql Linux

堆排序总结

发表于 2020-02-28 | 分类于 算法题总结 | 0 | 阅读次数 259
  1. 默认将arr数组按照广度优先遍历的方式形成一个二叉树,该树满足以下特性:
  • 如果含有子节点leftChildIndex的父节点的序号为parentIndex,arr总长度为len,则
  • 对于任意parentIndex,均满足 parentIndex <= (len-1)/2,即叶子节点最多有 len - (len-1)/2
  • leftChildIndex = 2*parentIndex + 1, 这是由每一层x的结点数都是 Math.pow(2, x)决定的
  1. 从父节点最大的序号开始依次遍历各个子树,使得每个子树都是大根堆结构,需要先从子节点中找到最大的值,然后和父节点比对,如果交换了数据,还需要向下调整大根堆结构
  2. 每次将大根堆的头结点的数据和最后一个叶子结点交换,交换后剪掉该叶子结点,并从头结点调整大根堆结构,循环直到大根堆只有一个结点为止。
package com.example.demo;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {10,2,3,6,7,4,5,7,8,9};

        heapSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void heapSort(int[] arr) {
        int len = arr.length;
        //(arr.length-1)/2的index是第一个有子结点的父结点
        for(int i=(len-1)/2; i>=0;i--) {
            adjustHeap(arr, i, len);
        }
        for(int i = len-1;i>0;i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     *
     * @param arr 将arr调成成为 adjustLength 内的、子树的头结点序号是parentIndex的大根堆,
     * @param parentIndex 需要调整arr的范围,超过这个范围说明已经排序好了
     * @param adjustLength 子树的头结点序号是parentIndex,调整后该子树为大根堆
     */
    private static void adjustHeap(int[] arr, int parentIndex, int adjustLength) {
        int selectedIndex = parentIndex*2+1;
        int needAdjustNum = arr[parentIndex];
        while(selectedIndex < adjustLength) {
            int rightChildIndex = selectedIndex+1;
            if(rightChildIndex<adjustLength && arr[rightChildIndex] > arr[selectedIndex]) {
                selectedIndex = rightChildIndex;
            }
            if(needAdjustNum >= arr[selectedIndex]) {
                break;
            } else {
                arr[parentIndex] = arr[selectedIndex];
                parentIndex = selectedIndex;
                selectedIndex = parentIndex*2+1;
            }
        }
        arr[parentIndex] = needAdjustNum;
    }
}
  • 本文作者: RuiCode
  • 本文链接: https://www.ruicode.cn/archives/堆排序总结
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 操作系统 # 并发 # 排序 # 网络 # 源码分析 # 二分法 # 面试 # 不重复算法 # 指针移动 # java # 算法 # mysql # Linux
【面试经】JAVA并发编程2--线程安全性、AQS、线程池
【面试经】操作系统内存管理1 -- 基本分页、分段、段页式
  • 文章目录
  • 站点概览
RuiCode

RuiCode

19 日志
5 分类
13 标签
Creative Commons
© 2021 RuiCode
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4

冀公网安备 13050002001906号