en造数据结构与算法C# 之 堆排序

堆的特点 

堆排序有两个分类:大顶堆,小顶堆

比如大顶堆就是说所有根节点的值都比左右子节点大

en造数据结构与算法C# 二叉排序树 泛型类的基本构成-CSDN博客

en造数据结构与算法C# 之 二叉排序树的增/查-CSDN博客

en造数据结构与算法C# 之 二叉排序树的删除-CSDN博客

 

堆排序的思路

堆构成

以大顶堆为例,对于索引从0开始的数组,其实现思路如下:

堆构成,首先是找到非叶子节点的子树

关键:完全二叉树的性质

非叶子节点的索引为(0,n/2-1),向下取整

叶子节点的索引从(n/2,n-1),向下取整

之后将根节点与两个子节点比较后,看是否交换,之后依次向上找子树,不断递归调整

        

对于一个数组,堆构成的方法为,其中n是数组长度

  static void Heapify(int[] array, int n, int i) {
  int largest = i; // 初始化最大值为根节点
  int left = 2 * i + 1; // 左子节点
  int right = 2 * i + 2; // 右子节点

  // 如果左子节点大于根节点
  if (left < n && array[left] > array[largest]) {
      largest = left;
  }

  // 如果右子节点大于最大值节点
  if (right < n && array[right] > array[largest]) {
      largest = right;
  }

  // 如果最大值不是根节点
  if (largest != i) {
      int swap = array[i];
      array[i] = array[largest];
      array[largest] = swap;

      // 递归地调整受影响的子树
      Heapify(array, n, largest);
  }

堆排序

这一步是在数组中利用上面的构成方法,进行堆的排序

首先,先执行一次构成堆的方法,将最大的值拿到树顶

其次,因为排序,所以需要将数值大的元素和最后一位交换

然后,将首位和末尾的数值进行交换,再进行一次堆构成的方法,并且忽略最后一位

以此类推

    static void HeapSorts(int[] array) {
        int n = array.Length;

        // 构建堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            Heapify(array, n, i);
        }

        // 一个个取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶(最大值)与堆的最后一个元素交换
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // 调整堆
            Heapify(array, i, 0);
        }
    }

总览: 

using System;

class Program
{
    static void Main()
    {
        int[] array = { 50, 10, 200, 30, 70, 40, 100, 60, 20, 65, 5 };
        HeapSort(array);
        Console.WriteLine(string.Join(", ", array));
    }

    static void HeapSort(int[] array)
    {
        int n = array.Length;

        // 构建堆
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(array, n, i);
        }

        // 一个个取出元素
        for (int i = n - 1; i > 0; i--)
        {
            // 将当前堆顶(最大值)与堆的最后一个元素交换
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // 调整堆
            Heapify(array, i, 0);
        }
    }

    static void Heapify(int[] array, int n, int i)
    {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点大于根节点
        if (left < n && array[left] > array[largest])
        {
            largest = left;
        }

        // 如果右子节点大于最大值节点
        if (right < n && array[right] > array[largest])
        {
            largest = right;
        }

        // 如果最大值不是根节点
        if (largest != i)
        {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

            // 递归地调整受影响的子树
            Heapify(array, n, largest);
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/891674.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用激光跟踪仪提升码垛机器人精度

标题1.背景 码垛机器人是一种用于工业自动化的机器人&#xff0c;专门设计用来将物品按照一定的顺序和结构堆叠起来&#xff0c;通常用于仓库、物流中心和生产线上&#xff0c;它们可以自动执行重复的、高强度的搬运和堆垛任务。 图1 码垛机器人 传统调整码垛机器人的方法&a…

Qt - QMenu

QMenu 1、menu转string输出 //GlobalEnum.h #include <QObject> #include <QMetaEnum> class GlobalEnum : public QObject {Q_OBJECT public:EnumTest();enum Enum_Test{ZhangSan 0,WangWu,};Q_ENUM(Enum_Test) };#define EnumToString(e) \ QMetaEnum::fromTy…

前端vue部署网站

这里讲解一下前端vue框架部署网站&#xff0c;使用工具是 xshell 和 xftp &#xff08;大家去官网安装免费版的就行了&#xff09; 服务器 我使用的阿里云服务器&#xff0c;买的是 99 一年的&#xff0c;淘宝有新手9.9 一个月服务器。可以去用&#xff0c;学生的话是有免费三…

【优选算法】(第三十六篇)

目录 ⼆叉树的锯⻮形层序遍历&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 ⼆叉树的最⼤宽度&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 ⼆叉树的锯⻮形层序遍历&#xff08;medium&#xff09; 题目解析 1.题目链接&#xf…

zabbix7.0配置中文界面

Zabbix 是一个广泛使用的开源监控解决方案&#xff0c;支持多种语言界面。本文将详细介绍如何配置 Zabbix 以使用中文界面&#xff0c;从而提高用户体验和可读性。 1. 环境准备 在开始配置之前&#xff0c;请确保你已经安装并运行了 Zabbix 服务器、前端和数据库。如果你还没有…

c++中,经常需要用来获取用户输入的写法,或者暂停【防止终端退出】

目录 1. 使用 cin.get() 暂停程序 2. 使用 std::cin.ignore() 结合 std::cin.get() 暂停程序 3. 使用 system("pause")&#xff08;仅限 Windows&#xff09; 4. 使用循环和 cin.get() 结合等待任意输入 5. 使用 cin >> 获取用户输入 为了防止终端窗口在程…

亚信安全亮相中国移动全球合作伙伴大会 AI+安全焕新变革原力

近日&#xff0c;2024中国移动全球合作伙伴大会在广州盛大召开。以“智焕新生 共创AI时代”为主题&#xff0c;携手数百位世界500强企业、国内外知名企业齐聚广州&#xff0c;共商融合创新&#xff0c;共谋AI未来&#xff0c;开启中国式现代化建设的新征程。亚信安全作为中国移…

QT文件操作【记事本】

mainwindow.h核心函数 QFileDialog::getOpenFileName()QFileDialog::getSaveFileName() #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include<QFileDialog> #include<QMessageBox> #include<QDebug> #include<QFile> #…

U9销售订单不能带出最新价格出来

业务员突然说系统带不出来销售价格。了解之后&#xff0c;不是带不出来价格&#xff0c;是做了价格调整之后&#xff0c;最新价格没有匹配出来&#xff0c;带出来的价格是历史价格。检查&#xff0c;分析相关的单据&#xff0c;生效日期&#xff0c;失效日期&#xff0c;审核状…

使用 python 下载 bilibili 视频

本文想要达成的目标为&#xff1a;运行 python 代码之后&#xff0c;在终端输入视频链接&#xff0c;可自动下载高清 1080P 视频并保存到相应文件夹。 具体可分为两大步&#xff1a;首先&#xff0c;使用浏览器开发者工具 F12 获取请求链接相关信息&#xff08;根据 api 接口下…

从加载到对话:使用 Llama-cpp-python 本地运行量化 LLM 大模型(GGUF)

&#xff08;无需显卡&#xff09;使用 Llama-cpp-python 在本地加载具有 70 亿参数的 LLM 大语言模型&#xff0c;通过这篇文章你将学会用代码创建属于自己的 GPT。 建议阅读完 19a 的「前言」和「模型下载」部分后再进行本文的阅读。 代码文件下载&#xff1a;Llama-cpp-pyth…

Vue3 + TypeScript + Vite + Echarts

Vue3 TypeScript Vite Echarts 1、创建工程 npm create vitelatestcd echarts npm install npm run dev2、安装项目依赖模块 npm install types/node --save-devnpm install vue-router4npm install animate.css --save npm install gsap --savenpm install fetch --save …

跨境电商干货:Etsy选品及相关运营技巧分享

Etsy作为一个吸引了全球将近一亿消费者的电子商务平台&#xff0c;因其聚焦小众、原创、设计产品的特点而拥有相当不错的流量和潜力&#xff0c;如果需要优化自己的Etsy店铺选品工作&#xff0c;可以参考以下技巧。 一、选品方向 1.按需求 Etsy主张售卖富有创意的、由卖家制作…

三电平逆变器:技术原理与实际应用

三电平逆变器&#xff1a;技术原理与实际应用&#xff08;网盘https://pan.baidu.com/s/1KRV4DBMChwZiu5lKgo0bEA 提取码 8v8p&#xff09; 中点钳位三电平逆变器的特性 优点 1、在换流过程中&#xff0c;每个功率半导体器件所承受的电压均为Ud/2。这有助于逆变器电压等级和…

VScode中CMake无高亮(就是没有补全的提示)

在我学的过程中我发现我的CMake是这样的&#xff0c;如下图 但在教学视频里是这样的&#xff08;如下图&#xff09; 这非常的难受&#xff0c;所以疯狂的找&#xff0c;最后是CMake报错有 原因就是&#xff1a;本地没有配置环境变量&#xff0c;解决方法是下一个cmake然后直接…

【C】分支与循环2--while/for/do-while/goto以及break和continue在不同循环中的辨析~

分支与循环 while循环 if与while的对比 if(表达式)语句&#xff1b;while(表达式)语句&#xff1b;下面来看一个例子&#xff1a; 用 if 写&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() {if (1)printf("hehe");//if后面条…

【千库网-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

3、Docker搭建MQTT及Spring Boot 3.x集成MQTT

一、前言 本篇主要是围绕着两个点&#xff0c;1、Docker 搭建单机版本 MQTT&#xff08;EMQX&#xff09;&#xff0c;2、Spring Boot 3.x 集成 MQTT&#xff08;EMQX&#xff09;&#xff1b; 而且这里的 MQTT&#xff08;EMQX&#xff09;的搭建也只是一个简单的过程&#x…

uibot发送邮件:自动化邮件发送教程详解!

uibot发送邮件的操作指南&#xff1f;uibot发送邮件的两种方式&#xff1f; 在现代办公环境中&#xff0c;自动化流程的引入极大地提高了工作效率。uibot发送邮件功能成为了许多企业和个人实现邮件自动化发送的首选工具。AokSend将详细介绍如何使用uibot发送邮件。 uibot发送…

RHCE的学习(1)

一、 Linux的例行性工作 场景&#xff1a; 生活中&#xff0c;我们有太多场景需要使用到闹钟&#xff0c;比如早上 7 点起床&#xff0c;下午 4 点开会&#xff0c;晚上 8 点购物&#xff0c;等等。 在 Linux 系统里&#xff0c;我们同样也有类似的需求。比如我们想在凌晨 1 …