数据结构的堆排序_数据结构冒泡排序算法

数据结构的堆排序_数据结构冒泡排序算法一、什么是堆排序1.堆,堆排序对于“堆”我们可以理解为具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆堆

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、什么是堆排序

1.堆,堆排序

对于“”我们可以理解为具有以下性质的完全二叉树

  • 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆
  • 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

在排序时,一般升序采用大顶堆,降序采用小顶堆。

2.大顶堆

数据结构的堆排序_数据结构冒泡排序算法

我们可以看到,层数从小到大,节点的数字是越来越小的,映射到数组有:{50,45,40,20,25,35,30,10,15}

特点是arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]

3.小顶堆

image-20200714202759899

跟大顶堆相反,层数从小到大,节点的数字是越来越大,映射到数组:{10,20,15,25,50,30,40,35,45}

特点是:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]

二、堆排序的思路分析

1.概述

  • 将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。
  • 将其与末尾元素进行交换,此时末尾就为最大值。
  • 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。
  • 遍历构建大顶堆,在这过程中元素的个数逐渐减少,直到最后得到一个有序序列了.

2.举个例子

对数组{4,6,8,5,9}进行排序。

第一遍排序

  1. 我们从最后一个非叶子结点开始排序。第一个非叶子结点为arr.length/2-1=5/2-1=1,也就是元素6.,我们对他进行对比并调整位置;

    数据结构的堆排序_数据结构冒泡排序算法

  2. 在{6,5,4}中,5比6小,而9比6大,所以9和6交换位置;

    image-20200716171927431

  3. 接着找到第二个非叶子节点4,由于9是{9,4,8}这个树中最大的,故9与4交换位置

    image-20200716172640232

  4. 由于9与4交换位置打乱了原先{9,5,6}这棵树顺序,所以继续对新树{4,5,6}进行排序

    image-20200716172926921

  5. 由此得到了一个大顶堆,然后将堆顶元素9与末尾元素4进行交换,得到数组{4,6,8,5,9}

    image-20200716173427122

至此,第一遍排序已经完成,我们确定了最大元素9的位置

第二遍排序

第二遍排序开始时,最大元素9的位置已经确定,实际上要排序的数组变成了{4,6,8,5}

  1. 继续从6开始比较,{6,5}排序正常,所以接着比较{4,6,8},8是最大的,所以与4交换位置

    image-20200716184743652

  2. 由此得到了一个大顶堆,然后将堆顶元素8与末尾元素5进行交换,得到数组{8,6,4}

    image-20200716184933083

至此,第一遍排序已经完成,我们确定了最第二大元素8的位置

第三遍~第n遍排序

第二遍排序开始时,最大元素9和第二大元素8的位置已经确定,实际上要排序的数组变成了{5,6,4}

重复比较-排序-交换堆顶和队尾元素位置这一过程,直到最终获得有序数列

image-20200716185250532

三、代码实现

/**
 * @Author:CreateSequence
 * @Date:2020-07-16 16:53
 * @Description:堆排序
 */
public class HeapSort {

    /**
     * 对数组进行堆排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr) {
        //将无序数组构建成一个大/小顶堆
        //有几个非叶子节点就排序几次
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            sortHeap(arr,i,arr.length);
        }

        int temp = 0;
        //交换数组头尾元素,将最大的元素排沉到队尾
        for (int i = arr.length - 1; i > 0; i--) {
            //交换头尾元素
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            //1.交换完后,此时最大的元素在arr[0],最小的元素在arr[i],即确定了本次排序范围最大的数
            //2.然后对0~i-1的范围进行排序,重新获得的数组最小的元素在arr[0],最大的元素在arr[i-1]
            sortHeap(arr, 0, i);
            
            //3.接着进入下一次循环,重复步骤1,2,每次循环排序范围都缩小一位
        }

        return arr;
    }

    /**
     * 将以非叶子节点i为根节点的树调整为一个大顶堆
     * @param arr 要调整的数组
     * @param i 非叶子结点在数组中的下标
     * @param length 要调整的数组长度
     */
    public static int[] sortHeap(int[] arr, int i, int length) {
        if (arr == null || arr.length == 0) {
            throw new RuntimeException("数列必须至少有一个元素!");
        }

        //获取根节点值
        int temp = arr[i];

        //从左节点开始遍历
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            //比较左右节点大小,将j指向值大的节点
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            //比较将左右节点与父节点大小
            if (arr[j] > temp) {
                //如果子节点大于父节点,交换两节点位置
                arr[i] = arr[j];
                //然后继续从该子节点向下遍历
                i = j;
            }else {
                break;
            }
        }

        //结束循环时,arr[i]已经存放了以原arr[i]为根节点的树的最大值
        arr[i] = temp;

        return arr;
    }

}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170805.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 无刷直流电机模糊PID控制「建议收藏」

    无刷直流电机在克服了有刷直流电机机械换相缺点的同时,又具有结构简单、运行可靠以及调速性能好等优点,在很多领域中得到了广泛的应用。本次课题阐述了无刷直流电机的基本结构、运行原理和数学模型,并以无刷直流电机为被控对象,根据电机的特点和控制要求确定了三闭环控制策略,分别是位置、转速及电流环控制三者之间实行串级连接。采用模糊PID控制理论,搭建无刷直流电机和控制器的仿真模型来验证电机控制策略的可行性,使要能使伺服控制器的具体性能满足:无静差,响应快,超调量小的设计要求。结合三闭环控制结构的特点,在位置环中采用模

  • 3分钟告诉你如何成为一名黑客?|零基础到黑客入门指南,你只需要掌握这五点能力

    3分钟告诉你如何成为一名黑客?|零基础到黑客入门指南,你只需要掌握这五点能力三分钟带各位揭秘黑客究竟是什么,以及想要成为黑客都需要具备哪些能力?

  • 软考网络工程师备考经验

    软考网络工程师备考经验软考网工的备考经验文章目录讲废话题型备考经验上午题下午题刷题软件讲废话本人大三,网络工程专业。11月8日考的试,11月18日出的成绩。上午53,下午54,但是成绩还是让我不太满意鸭!!!最开始大二的时候从老师的嘴里听到的有能力的去考软考(其实我也没什么能力,是个老菜逼了。。。)所以下课的时候就了解了一下。软考有初级、中级、高级。初级是网管员没什么技术含量挺简单的,高级呢,要写论文还没项目经验也不会写论文,所以就选择了中级网络工程师。题型分为上午题(75道选择题)、下午题(案例分析4大题7

  • Windows CMD命令总结及使用介绍

    Windows CMD命令总结及使用介绍

  • 基尼系数直接计算法_基尼系数简单的计算方法

    基尼系数直接计算法_基尼系数简单的计算方法使用两种方法,通过python计算基尼系数。在sql中如何计算基尼系数,可以查看我的另一篇文章。两篇文章取数相同,可以结合去看。文章中方法1的代码来自于:(加入了一些注释,方便理解)。为精确计算。如果对于基尼系数概念不太清楚,可以看原文的第一部分。http://www.cnblogs.com/longwind09/p/8047539.html方法2和3借鉴资料:方法2和3…

    2022年10月13日
  • 详细说明Ipad1 4.3.5的越狱过程

    详细说明Ipad1 4.3.5的越狱过程前言,使用Ipad很久了,但是都是老实巴交的使用APPLE提供的功能,没有使用很多的软件,因为要收费,只是看一看pdf和视频。但是时间长了,感觉不新鲜了,看了很久越狱的好处和弊端,心里痒痒的。最好终于手痒痒了,开始动手了。但是开始不顺利,我一直是跟着升级固件,最后升级到4.3.1

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号