详解如何在Java中实现堆排序算法

目录
  • 算法描述
  • 实现代码
  • 测试代码

算法描述

堆排序算法的描述如下：

  • 将待排序的数组调整为最大堆，此时未排序的长度 N 为数组的长度，调整的过程就是倒序将数组的前 N/2 个元素下沉的过程，每次下沉都会将较大的元素带到上面，最终将数组变为最大堆；
  • 弹出最大堆的堆顶元素并将其移动到数组的最后面，将原本最后面的元素放到堆顶，然后将未排序的长度 N - 1，调整数组的前 N 个元素为最大堆；
  • 重复步骤 2 直到未排序的长度为 0.

实现代码

package com.zhiyiyo.collection.sort;

import java.util.Arrays;

public class HeapSort extends BaseSort {
    @Override
    public void sort(Comparable[] array) {
        int N = array.length;

        // 创建最大堆
        for (int i = N / 2; i >= 0; i--) {
            sink(array, i, N);
        }

        // 就地排序
        while (N > 0) {
            // 将最大的元素移动到数组的尾部，同时将未排序的长度-1
            swap(array, 0, --N);
            // 调整最大堆
            sink(array, 0, N);
        }
    }

    /**
     * 下沉元素
     *
     * @param array 数组
     * @param k     下沉的元素索引
     */
    private void sink(Comparable[] array, int k, int N) {
        while (2 * k + 1 < N) {
            int j = 2 * k + 1;
            if (j < N - 1 && less(array[j], array[j + 1])) j++;
            if (!less(array[k], array[j])) break;
            swap(array, k, j);
            k = j;
        }
    }
}

抽象类 BaseSort 的代码为：

package com.zhiyiyo.collection.sort;

/**
 * 数组排序抽象类
 */
public abstract class BaseSort {
    public abstract void sort(Comparable[] array);

    /**
     * 交换数组元素
     *
     * @param array 数组
     * @param a     数组下标 a
     * @param b     数组下标 b
     */
    protected static void swap(Comparable[] array, int a, int b) {
        Comparable tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    protected static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

}

测试代码

package com.zhiyiyo.collection.sort;

import org.junit.Test;

import java.util.Arrays;

public class HeapSortTest {

    @Test
    public void sort() {
        Integer[] array = {5, 10, 9, 6, 8, 7, 2, 1, 4, 3};
        new HeapSort().sort(array);
        System.out.println(Arrays.toString(array));
    }
}

最终排序结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，以上~

到此这篇关于详解如何在Java中实现堆排序算法的文章就介绍到这了,更多相关Java堆排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • JAVA十大排序算法之堆排序详解

    JAVA十大排序算法之堆排序详解

    目录 堆排序 知识补充 二叉树 满二叉树 完全二叉树 二叉堆 代码实现 时间复杂度 算法稳定性 思考 总结 堆排序 这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树 堆中某个结点的值总是不大于或不小于其父结点的值 知识补充 二叉树 树中节点的子节点不超过2的有序树 满二叉树 二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树 如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有

  • Java算法之堆排序代码示例

    Java算法之堆排序代码示例

    堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

  • Java实现堆排序和图解

    Java实现堆排序和图解

    目录 堆排序基本介绍 堆排序基本思想 堆排序图解 步骤一 步骤二 代码实现 总结 堆排序基本介绍 1.堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序. 2.堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系. 3.每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆 4.大顶堆举例说明 大顶堆特点:arr[i]

  • JAVA堆排序算法的讲解

    预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子 该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是: 大顶

  • 图解Java排序算法之堆排序

    图解Java排序算法之堆排序

    目录 预备知识 堆排序 堆 堆排序基本思想及步骤 再简单总结下堆排序的基本思路: 总结 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面

  • Java堆排序算法详解

    堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+

  • 详解如何在Java中实现堆排序算法

    目录 算法描述 实现代码 测试代码 算法描述 堆排序算法的描述如下: 将待排序的数组调整为最大堆,此时未排序的长度 N 为数组的长度,调整的过程就是倒序将数组的前 N/2 个元素下沉的过程,每次下沉都会将较大的元素带到上面,最终将数组变为最大堆: 弹出最大堆的堆顶元素并将其移动到数组的最后面,将原本最后面的元素放到堆顶,然后将未排序的长度 N - 1,调整数组的前 N 个元素为最大堆: 重复步骤 2 直到未排序的长度为 0. 实现代码 package com.zhiyiyo.collection

  • 详解如何在Java中调用Python程序

    Java中调用Python程序 1.新建一个Maven工程,导入如下依赖 <dependency> <groupId>org.python</groupId> <artifactId>jython-standalone</artifactId> <version>2.7.0</version> </dependency> 2.在java中直接执行python代码片段 import org.python.util

  • 详解如何在Java中加密和解密zip文件

    目录 依赖 压缩一个文件 压缩多个文件 压缩一个目录 创建一个分割的压缩文件 提取所有文件 提取单个文件 总结 依赖 让我们先把 zip4j 依赖关系添加到我们的 pom.xml 文件中. <dependency>     <groupId>net.lingala.zip4j</groupId>     <artifactId>zip4j</artifactId>     <version>2.9.0</version>

  • 详解如何在pyqt中通过OpenCV实现对窗口的透视变换

    窗口的透视变换效果    当我们点击Win10的UWP应用中的小部件时,会发现小部件会朝着鼠标点击位置凹陷下去,而且不同的点击位置对应着不同的凹陷情况,看起来就好像小部件在屏幕上不只有x轴和y轴,甚至还有一个z轴.要做到这一点,其实只要对窗口进行透视变换即可.下面是对Qt的窗口和按钮进行透视变换的效果: 具体代码    1.下面先定义一个类,它的作用是将传入的 QPixmap 转换为numpy 数组,然后用 opencv 的 warpPerspective 对数组进行透视变换,最后再将 nump

  • 详解如何在Javascript中使用Object.freeze()

    Object.freeze() Object.freeze() 方法可以冻结一个对象.一个被冻结的对象再也不能被修改:冻结了一个对象则不能向这个对象添加新的属性,不能删除已有属性,不能修改该对象已有属性的可枚举性.可配置性.可写性,以及不能修改已有属性的值.此外,冻结一个对象后该对象的原型也不能被修改.freeze() 返回和传入的参数相同的对象 用法 const objectExample = { prop1: 20, prop2: "羊先生" }; // 默认情况下,我们可以根据需

  • 详解如何把Java中if-else代码重构成高质量代码

    为什么我们写的代码都是if-else? 程序员想必都经历过这样的场景:刚开始自己写的代码很简洁,逻辑清晰,函数精简,没有一个if-else, 可随着代码逻辑不断完善和业务的瞬息万变:比如需要对入参进行类型和值进行判断:这里要判断下对象是否为null:不同类型执行不同的流程. 落地到具体实现只能不停地加if-else来处理,渐渐地,代码变得越来越庞大,函数越来越长,文件行数也迅速突破上千行,维护难度也越来越大,到后期基本达到一种难以维护的状态. 虽然我们都很不情愿写出满屏if-else的代码,可逻

  • 详解如何在C#中使用投影(Projection)

    详解如何在C#中使用投影(Projection)

    投影(Projection) 是一种可以将查询结果进行 塑性 的一种操作,你可以使用 投影 将一个 object 转成仅包含你需要属性的新对象,这篇文章中,我们就一起看看如何使用 投影 功能. C# 中的投影 LINQ 集成查询中有两个支持投影的扩展方法,分别为: Select 和 SelectMany 操作,可以用它们投影单个或者多个属性,或者投影查询的结果集到一个新的匿名类型中,还可以在投影的过程中执行: 再计算,过滤,或者其他一些必要的操作. Select 投影 为了演示目的,我先构造一个

  • 详解如何在Flutter中集成华为认证服务

    详解如何在Flutter中集成华为认证服务

    最近发现华为AGC认证服务支持Flutter框架了,期待这个平台的支持已经很久了,所以迫不及待接入了,关联了自己的邮箱等账号. 集成步骤 安装flutter环境 a) 下载Flutter sdk包,地址:https://flutter.dev/docs/get-started/install/windows 将压缩包解压到任意文件夹,例如D:\Flutter b) 将flutter命令文件添加到环境变量中,此处我添加的Path为D:\Flutter\flutter_windows_1.22.2-

  • 详解如何在Flutter中获取设备标识符

    详解如何在Flutter中获取设备标识符

    目录 使用 platform_device_id 应用预览 代码 使用 device_info_plus 应用预览 代码 结论 本文将引导您完成 2 个示例,演示如何在 Flutter 中获取设备标识符 使用 platform_device_id 如果您只需要运行应用程序的设备的 id,最简单快捷的解决方案是使用platform_device_id包.它适用于 Android (AndroidId).iOS (IdentifierForVendor).Windows (BIOS UUID).ma

  • 详解如何在SpringBoot中自定义参数解析器

    目录 前言 1.自定义参数解析器 2.PrincipalMethodArgumentResolver 3.RequestParamMapMethodArgumentResolver 4.小结 前言 在一个 Web 请求中,参数我们无非就是放在地址栏或者请求体中,个别请求可能放在请求头中. 放在地址栏中,我们可以通过如下方式获取参数: String javaboy = request.getParameter("name "); 放在请求体中,如果是 key/value 形式,我们可以通

随机推荐