程序员经验分享-hwhale

算法 - 堆排序（C#）

2023-11-14
[csharp]  view plain  copy  print ?
  1. // --------------------------------------------------------------------------------------------------------------------  
  2. // <copyright file="Program.cs" company="Chimomo's Company">  
  3. //  
  4. // Respect the work.  
  5. //  
  6. // </copyright>  
  7. // <summary>  
  8. //  
  9. // Heap sort.  
  10. //  
  11. // 堆排序是一种选择排序，时间复杂度为O(nlog<sub>2</sub>n)。  
  12. // 堆排序的特点是：在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。  
  13. //  
  14. // 基本思想  
  15. // 1.将待排序数组调整为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。  
  16. // 2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置列入有序区，然后将新的无序区调整为大根堆。  
  17. // 3.重复操作，直到无序区消失为止。  
  18. // 初始时，整个数组为无序区。每一次交换，都是将大根堆的堆顶元素换入有序区，以保证有序区是有序的。  
  19. //  
  20. // </summary>  
  21. // --------------------------------------------------------------------------------------------------------------------  
  22.   
  23. namespace CSharpLearning  
  24. {  
  25.     using System;  
  26.   
  27.     /// <summary>  
  28.     /// The program.  
  29.     /// </summary>  
  30.     public static class Program  
  31.     {  
  32.         /// <summary>  
  33.         /// 程序入口点。  
  34.         /// </summary>  
  35.         public static void Main()  
  36.         {  
  37.             int[] a = { 1, 14, 6, 2, 8, 66, 9, 3, 0, 10, 5, 34, 76, 809, 4, 7 };  
  38.             Console.WriteLine("Before Heap Sort...");  
  39.             foreach (int i in a)  
  40.             {  
  41.                 Console.Write(i + " ");  
  42.             }  
  43.   
  44.             Console.WriteLine("\r\n--------------------");  
  45.             Console.WriteLine("In Heap Sort...");  
  46.             HeapSort(a);  
  47.             Console.WriteLine("--------------------");  
  48.             Console.WriteLine("After Heap Sort...");  
  49.             foreach (int i in a)  
  50.             {  
  51.                 Console.Write(i + " ");  
  52.             }  
  53.   
  54.             Console.WriteLine(string.Empty);  
  55.         }  
  56.   
  57.         /// <summary>  
  58.         /// 堆排序方法。  
  59.         /// </summary>  
  60.         /// <param name="a">  
  61.         /// 待排序数组。  
  62.         /// </param>  
  63.         private static void HeapSort(int[] a)  
  64.         {  
  65.             BuildMaxHeap(a); // 建立大根堆。  
  66.             Console.WriteLine("Build max heap:");  
  67.             foreach (int i in a)  
  68.             {  
  69.                 Console.Write(i + " "); // 打印大根堆。  
  70.             }  
  71.   
  72.             Console.WriteLine("\r\nMax heap in each iteration:");  
  73.             for (int i = a.Length - 1; i > 0; i--)  
  74.             {  
  75.                 Swap(ref a[0], ref a[i]); // 将堆顶元素和无序区的最后一个元素交换。  
  76.                 MaxHeaping(a, 0, i); // 将新的无序区调整为大根堆。  
  77.   
  78.                 // 打印每一次堆排序迭代后的大根堆。  
  79.                 for (int j = 0; j < i; j++)  
  80.                 {  
  81.                     Console.Write(a[j] + " ");  
  82.                 }  
  83.   
  84.                 Console.WriteLine(string.Empty);  
  85.             }  
  86.         }  
  87.   
  88.         /// <summary>  
  89.         /// 由底向上建堆。由完全二叉树的性质可知，叶子结点是从index=a.Length/2开始，所以从index=(a.Length/2)-1结点开始由底向上进行大根堆的调整。  
  90.         /// </summary>  
  91.         /// <param name="a">  
  92.         /// 待排序数组。  
  93.         /// </param>  
  94.         private static void BuildMaxHeap(int[] a)  
  95.         {  
  96.             for (int i = (a.Length / 2) - 1; i >= 0; i--)  
  97.             {  
  98.                 MaxHeaping(a, i, a.Length);  
  99.             }  
  100.         }  
  101.   
  102.         /// <summary>  
  103.         /// 将指定的结点调整为堆。  
  104.         /// </summary>  
  105.         /// <param name="a">  
  106.         /// 待排序数组。  
  107.         /// </param>  
  108.         /// <param name="i">  
  109.         /// 需要调整的结点。  
  110.         /// </param>  
  111.         /// <param name="heapSize">  
  112.         /// 堆的大小，也指数组中无序区的长度。  
  113.         /// </param>  
  114.         private static void MaxHeaping(int[] a, int i, int heapSize)  
  115.         {  
  116.             int left = (2 * i) + 1; // 左子结点。  
  117.             int right = 2 * (i + 1); // 右子结点。  
  118.             int large = i; // 临时变量，存放大的结点值。  
  119.   
  120.             // 比较左子结点。  
  121.             if (left < heapSize && a[left] > a[large])  
  122.             {  
  123.                 large = left;  
  124.             }  
  125.   
  126.             // 比较右子结点。  
  127.             if (right < heapSize && a[right] > a[large])  
  128.             {  
  129.                 large = right;  
  130.             }  
  131.   
  132.             // 如有子结点大于自身就交换，使大的元素上移；并且把该大的元素调整为堆以保证堆的性质。  
  133.             if (i != large)  
  134.             {  
  135.                 Swap(ref a[i], ref a[large]);  
  136.                 MaxHeaping(a, large, heapSize);  
  137.             }  
  138.         }  
  139.   
  140.         /// <summary>  
  141.         /// 交换两个整数的值。  
  142.         /// </summary>  
  143.         /// <param name="a">整数a。</param>  
  144.         /// <param name="b">整数b。</param>  
  145.         private static void Swap(ref int a, ref int b)  
  146.         {  
  147.             int tmp = a;  
  148.             a = b;  
  149.             b = tmp;  
  150.         }  
  151.     }  
  152. }  
  153.   
  154. // Output:  
  155. /* 
  156. Before Heap Sort... 
  157. 1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7 
  158. -------------------- 
  159. In Heap Sort... 
  160. Build max heap: 
  161. 809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2 
  162. Max heap in each iteration: 
  163. 76 14 66 7 10 34 9 3 0 8 5 2 1 6 4 
  164. 66 14 34 7 10 4 9 3 0 8 5 2 1 6 
  165. 34 14 9 7 10 4 6 3 0 8 5 2 1 
  166. 14 10 9 7 8 4 6 3 0 1 5 2 
  167. 10 8 9 7 5 4 6 3 0 1 2 
  168. 9 8 6 7 5 4 2 3 0 1 
  169. 8 7 6 3 5 4 2 1 0 
  170. 7 5 6 3 0 4 2 1 
  171. 6 5 4 3 0 1 2 
  172. 5 3 4 2 0 1 
  173. 4 3 1 2 0 
  174. 3 2 1 0 
  175. 2 0 1 
  176. 1 0 
  177. 0 
  178. -------------------- 
  179. After Heap Sort... 
  180. 0 1 2 3 4 5 6 7 8 9 10 14 34 66 76 809 

  1. */  
   转自：http://blog.csdn.net/troubleshooter/article/details/4650122

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

算法

堆排序

算法 - 堆排序（C#） 的相关文章

  • 是否有与 posix_memalign 对应的 C++ 版本？

    当我打电话时posix memalign http man7 org linux man pages man3 posix memalign 3 html为类型的对象分配对齐的内存Foo在我的 C 代码中 我需要做一个reinterpret

  • CLR 2.0 与 4.0 性能比较？

    如果在 CLR 4 0 下运行 为 CLR 2 0 编译的 NET 程序会运行得更快吗 应用程序配置

  • 计算 XML 中特定 XML 节点的数量

    请参阅此 XML

  • 使用 C# 登录《我的世界》

    我正在尝试为自己和一些朋友创建一个简单的自定义 Minecraft 启动器 我不需要启动 Minecraft 的代码 只需要登录的实际代码行 例如 据我所知 您过去可以使用 string netResponse httpGET https

  • 如何判断计算机是否已重新启动？

    我曾经使用过一个命令行 SMTP 邮件程序 作为试用版的限制 它允许您在每个 Windows 会话中最多接收 10 封电子邮件 如果您重新启动计算机 您可能还会收到 10 个以上 我认为这种共享软件破坏非常巧妙 我想在我的应用程序中复制它

  • JNI 将 Char* 2D 数组传递给 JAVA 代码

    我想从 C 代码通过 JNI 层传递以下指针数组 char result MAXTEST MAXRESPONSE 12 12 8 3 29 70 5 2 42 42 在java代码中我写了以下声明 public static native

  • 为什么在 WebApi 上下文中在 using 块中使用 HttpClient 是错误的？

    那么 问题是为什么在 using 块中使用 HttpClient 是错误的 但在 WebApi 上下文中呢 我一直在读这篇文章不要阻止异步代码 https blog stephencleary com 2012 07 dont block

  • 从客户端访问 DomainService 中的自定义对象

    我正在使用域服务从 Silverlight 客户端的数据库中获取数据 在DomainService1 cs中 我添加了以下内容 EnableClientAccess public class Product public int produ

  • 使用 LINQ to SQL 时避免连接超时的最佳实践

    我需要知道在 net 应用程序中使用 LINQ to SQL 时避免连接超时的最佳实践 特别是在返回时IQueryable

  • 使用valgrind进行GDB远程调试

    如果我使用远程调试gdb我连接到gdbserver using target remote host 2345 如果我使用 valgrind 和 gdb 调试内存错误 以中断无效内存访问 我会使用 target remote vgdb 启动

  • IQueryable 单元或集成测试

    我有一个 Web api 并且公开了一个端点 如下所示 api 假期 name name 这是 Web api 的控制器 get 方法 public IQueryable

  • 在视口中查找 WPF 控件

    Updated 这可能是一个简单或复杂的问题 但在 wpf 中 我有一个列表框 我用一个填充数据模板从列表中 有没有办法找出特定的数据模板项位于视口中 即我已滚动到其位置并且可以查看 目前我连接到了 listbox ScrollChange

  • 在 NaN 情况下 to_string() 可以返回什么

    我使用 VS 2012 遇到了非常令人恼火的行为 有时我的浮点数是 NaN auto dbgHelp std to string myFloat dbgHelp最终包含5008角色 你不能发明这个东西 其中大部分为0 最终结果是 0 INF

  • C++ int 前面加 0 会改变整个值

    我有一个非常奇怪的问题 如果我像这样声明一个 int int time 0110 然后将其显示到控制台返回的值为72 但是当我删除前面的 0 时int time 110 然后控制台显示110正如预期的那样 我想知道两件事 首先 为什么它在

  • C++ 中的双精度型数字

    尽管内部表示有 17 位 但 IEE754 64 位 浮点应该正确表示 15 位有效数字 有没有办法强制第 16 位和第 17 位为零 Ref http msdn microsoft com en us library system dou

  • Unity：通过拦截将两个接口注册为一个单例

    我有一个实现两个接口的类 我想对该类的方法应用拦截 我正在遵循中的建议Unity 将两个接口注册为一个单例 https stackoverflow com questions 1394650 unity register two inter

  • C++ new * char 不为空

    我有一个问题 我在 ASIO 中开发服务器 数据包采用尖头字符 当我创建新字符时 例如char buffer new char 128 我必须手动将其清理为空 By for int i 0 i lt 128 i buffer i 0x00

  • 使用 C 在 OS X 中获取其他进程的 argv

    我想获得其他进程的argv 例如ps 我使用的是在 Intel 或 PowerPC 上运行的 Mac OS X 10 4 11 首先 我阅读了 ps 和 man kvm 的代码 然后编写了一些 C 代码 include

  • GCC 的“-Wl,option”和“-Xlinker option”语法之间有区别吗？

    我一直在查看一些配置文件 并且看到它们都被使用 尽管在不同的体系结构上 如果您在 Linux 机器上使用 GCC 将选项传递给链接器的两种语法之间有区别吗 据我所知 阅读 GCC 手册时 他们的解释几乎相同 From man gcc Xli

  • 灵气序列解析问题

    我在使用 Spirit Qi 2 4 编写解析器时遇到一些问题 我有一系列键值对以以下格式解析

随机推荐

  • qqkey获取原理_【逆向】QQkey盗号木马原理分析

    一 简介 QQkey是一段字符串 通过这段字符串在没有QQ登录密码的前提下你依然能够在浏览器中对别人QQ空间 邮箱等应用进行随意访问和操作 现在市面上已经有很多使用易语言编写的盗号木马 专门盗取别人的QQkey 通过QQkey改绑关联了该邮

  • Robot Framework 自动化测试详解

    一 Robot Framework 简介 1 界面自动化测试工具 界面自动化测试 即UI自动化测试 比较常见的工具有 QTP AutoIt Selenium等 像QTP经历了很多版本 最新的版本好像叫UFT了 对初学者来说 录制回放是相当容

  • 搭建免费IP代理池

    声明 本文章中所有内容仅供学习交流 不可用于任何商业用途和非法用途 否则后果自负 如有侵权 请联系作者立即删除 由于本人水平有限 如有理解或者描述不准确的地方 还望各位大佬指教 搭建代理池思路 思路来源 崔庆才大佬的爬虫书 代理从何而来 用

  • 网络安全面试必问

    项目经历 因为大家写的都是渗透相关 所以编故事也要编的圆润些 题材可以去freebuf看 https search freebuf com search search E6 8C 96 E6 B4 9E article 这里主要记录如何挖洞

  • 三类保留地址（私有地址）【个人笔记，仅供参考】

    A类 10 X X X是私有地址 私有地址就是在互联网上不使用 而被用在局域网络中的地址 127 X X X是保留地址 用做循环测试用的 B类 172 16 0 0 172 31 255 255是私有地址 169 254 X X是保留地址

  • 在Anaconda下安装并使用Pytorch，pillow，numpy等库及Python版本的匹配

    我在Anaconda下创建的新环境为 python 3 7 0 pytorch 1 8 0 pillow 9 5 0 numpy 1 21 5 能够正常运行 如果我这个版本够用的话可以按照这个版本进行安装 具体步骤如下 1 在Anacond

  • PROFINET从站设备描述文件

    目录 一 GSDML文件名格式 二 设备标识信息 三 设备支持的通讯周期时间 四 设备支持的槽位和数据模块 相信熟悉工业现场的工程师们 对于PROFIBUS和PROFINET这两个工业协议都不陌生 过去在使用PROFIBUS现场总线时 从站

  • matlab 专家pid,专家PID

    3 专家控制器 专家控制器的模型是整个仿真模型中的重点 其实质就是把专家规则用Matlab现有计算元件实现出来 当前一般的做法就是利用 IF THEN 语句来表述一条一条的专家规则 28 把单回路控制中的部分规则做成的专家控制器如下所示 图

  • 什么是Elastic Stack

    什么是Elastic Stack Elastic Stack是由ELK演化而来 ELK是三种软件的简称 分别是Elasticsearch logstash kibana组成 在发展的过程中 又有新成员Beats的加入 形成了Elastic

  • Hadoop运行模式 之 本地运行模式

    Hadoop的运行模式包括 本地模式 伪分布式模式以及完全分布式模式 Hadoop官网地址 https hadoop apache org 本次使用的Hadoop的版本是2 7 2 官网文档 https hadoop apache org

  • ssh-keygen 常用命令与参数

    ssh keygen 常用命令与参数 生成密钥 默认生成 2048 位 RSA 密钥 ssh keygen 生成 4096 位 RSA 密钥 ssh keygen t rsa b 4096 生成 521 位 ECDSA 密钥 ssh key

  • sql注入基础原理（超详细）

    一 Sql注入简介 Sql 注入攻击是通过将恶意的 Sql 查询或添加语句插入到应用的输入参数中 再在后台 Sql 服务器上解析执行进行的攻击 它目前黑客对数据库进行攻击的最常用手段之一 二 Web 程序三层架构 三层架构 3 tier a

  • qt信号槽之创建和连接自定义的槽

    在第一版的Qt设计器中 你可以创建你自定义的槽的信号并使他们连接起来 但是你不能直接实现你的槽 你不得不子集于该窗体 并在这个子集中对你自定义的槽编码 子集的方法依然有用 在某些情况下仍起作用 Make sense 但是现在你可以在Qt设计

  • R语言入门

    安装 R语言开源 安装很简单 此处带过 界面 R语言的使用简介 赋值命令 赋值符号为 lt 或 但是建议使用 lt x lt 10 赋值10给变量x R语言的数据类型 R是一种基于对象 object 的语言 在R中看到的一切事物都是对象 对

  • JAVA遇见HTML—JSP篇（六.JSP指令与动作元素）

    include指令 语法 代码示例 新建date jsp文件

  • TensorFlow2.0.0开发环境安装

    TensorFlow 框架支持多种常见的操作系统 如 Windows 10 Ubuntu 18 04 Mac OS 等等 同时也支持运行在 NVIDIA 显卡上的 GPU 版本和仅适用 CPU完成计算的 CPU 版本 我们以最为常见的 Wi

  • c语言练习49：有多少⼩于当前数字的数字

    有多少 于当前数字的数字 给你 个数组 nums 对于其中每个元素 nums i 请你统计数组中 它 的所有数字的数 换 之 对于每个 nums i 你必须计算出有效的 j 的数量 其中 j 满 j i 且nums j lt nums i

  • 【网络层】网络基础 -- IP协议

    引入 IP 协议头格式 网段划分 特殊的IP地址 IP地址的数量限制 私有IP地址和公网IP地址 分片与组装 如何分片与组装 引入 我们前面学习了传输层的相关知识 难道真的就是直接传送吗 当然不是 那TCP究竟做了什么 IP又扮演什么角色

  • Unity3d 制作一个简单的NPC对话系统

    制作一个简单的NPC对话系统 文章目录 制作一个简单的NPC对话系统 前言 效果展示 进入对话区域 开始对话 Inspector面板可调选项 准备工作 NPC UI 代码 完整代码 详细逻辑 开启对话 显示对话 头顶标识 头顶标识 后话 前

  • 算法 - 堆排序（C#）

    csharp view plain copy print

热门标签