程序员经验分享-hwhale

算法 - 快速排序（C#）

2023-11-17
[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. // The quick sort.  
  10. //  
  11. // 快速排序（QuickSort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
  12. //  
  13. // 设要排序的数组是a[0]...a[N-1]，首先任意选取一个数据（通常选用数组的首元素）作为关键数据，然后将所有比它小的数都放到它的前面，所有比它大的数都放到它的后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。  
  14. // 一趟快速排序的算法是：  
  15. // 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；  
  16. // 2）以数组首元素作为关键数据，赋值给pivot，即pivot=a[0]；  
  17. // 3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于pivot的值a[j]，将a[j]赋值给a[i]；  
  18. // 4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于pivot的值a[i]，将a[i]赋值给a[j]；  
  19. // 5）重复第3、4步，直到i==j；（在3、4步中，若没找到符合条件的值，即3中a[j]不小于pivot，4中a[i]不大于pivot的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。若找到符合条件的值，进行替换的时候i、j指针位置不变。）  
  20. //  
  21. // 快速排序的平均时间复杂度是：O(nlog<sub>2</sub>n)。  
  22. //  
  23. // </summary>  
  24. // --------------------------------------------------------------------------------------------------------------------  
  25.   
  26. namespace CSharpLearning  
  27. {  
  28.     using System;  
  29.   
  30.     /// <summary>  
  31.     /// The program.  
  32.     /// </summary>  
  33.     public static class Program  
  34.     {  
  35.         /// <summary>  
  36.         /// The main.  
  37.         /// </summary>  
  38.         public static void Main()  
  39.         {  
  40.             int[] a = { 101, 93, 856, 7, 62, 15, 84, 3, 298, 1256 };  
  41.             Console.WriteLine("Before Quick Sort:");  
  42.             foreach (int i in a)  
  43.             {  
  44.                 Console.Write(i + " ");  
  45.             }  
  46.   
  47.             Console.WriteLine("\r\n");  
  48.             Console.WriteLine("In Quick Sort:");  
  49.             QuickSort(a, 0, 9);  
  50.             Console.WriteLine("\r\nAfter Quick Sort:");  
  51.             foreach (int i in a)  
  52.             {  
  53.                 Console.Write(i + " ");  
  54.             }  
  55.   
  56.             Console.WriteLine(string.Empty);  
  57.         }  
  58.   
  59.         /// <summary>  
  60.         /// 快速排序。  
  61.         /// </summary>  
  62.         /// <param name="a">  
  63.         /// 待排序数组。  
  64.         /// </param>  
  65.         /// <param name="low">  
  66.         /// 待排序数组的排序起始位置。  
  67.         /// </param>  
  68.         /// <param name="high">  
  69.         /// 待排序数组的排序终止位置。  
  70.         /// </param>  
  71.         private static void QuickSort(int[] a, int low, int high)  
  72.         {  
  73.             if (low >= high)  
  74.             {  
  75.                 return;  
  76.             }  
  77.   
  78.             int pivot = QuickSortOnce(a, low, high);  
  79.   
  80.             // 输出每一次排序。  
  81.             foreach (int i in a)  
  82.             {  
  83.                 Console.Write(i + " ");  
  84.             }  
  85.   
  86.             Console.WriteLine(string.Empty);  
  87.   
  88.             // 对枢轴的左端进行排序。  
  89.             QuickSort(a, low, pivot - 1);  
  90.   
  91.             // 对枢轴的右端进行排序。  
  92.             QuickSort(a, pivot + 1, high);  
  93.         }  
  94.   
  95.         /// <summary>  
  96.         /// 一趟快速排序。  
  97.         /// </summary>  
  98.         /// <param name="a">  
  99.         /// 待排序数组。  
  100.         /// </param>  
  101.         /// <param name="low">  
  102.         /// 待排序数组的排序起始位置。  
  103.         /// </param>  
  104.         /// <param name="high">  
  105.         /// 待排序数组的排序终止位置。  
  106.         /// </param>  
  107.         /// <returns>  
  108.         /// 返回枢轴的位置。  
  109.         /// </returns>  
  110.         private static int QuickSortOnce(int[] a, int low, int high)  
  111.         {  
  112.             // 将首元素作为枢轴。  
  113.             int pivot = a[low];  
  114.             int i = low, j = high;  
  115.   
  116.             while (i < j)  
  117.             {  
  118.                 // 从右到左，寻找首个小于pivot的元素。  
  119.                 while (a[j] >= pivot && i < j)  
  120.                 {  
  121.                     j--;  
  122.                 }  
  123.   
  124.                 // 执行到此，j一定指向从右端起首个小于或等于pivot的元素。执行替换。  
  125.                 a[i] = a[j];  
  126.   
  127.                 // 从左到右，寻找首个大于pivot的元素。  
  128.                 while (a[i] <= pivot && i < j)  
  129.                 {  
  130.                     i++;  
  131.                 }  
  132.   
  133.                 // 执行到此，i一定指向从左端起首个大于或等于pivot的元素。执行替换。  
  134.                 a[j] = a[i];  
  135.             }  
  136.   
  137.             // 退出while循环，执行至此，必定是i==j的情况。i（或j）指向的即是枢轴的位置，定位该趟排序的枢轴并将该位置返回。  
  138.             a[i] = pivot;  
  139.             return i;  
  140.         }  
  141.     }  
  142. }  
  143.   
  144. // Output:  
  145. /* 
  146. Before Quick Sort: 
  147. 101 93 856 7 62 15 84 3 298 1256 
  148.  
  149. In Quick Sort: 
  150. 3 93 84 7 62 15 101 856 298 1256 
  151. 3 93 84 7 62 15 101 856 298 1256 
  152. 3 15 84 7 62 93 101 856 298 1256 
  153. 3 7 15 84 62 93 101 856 298 1256 
  154. 3 7 15 62 84 93 101 856 298 1256 
  155. 3 7 15 62 84 93 101 298 856 1256 
  156.  
  157. After Quick Sort: 
  158. 3 7 15 62 84 93 101 298 856 1256 
  159. */  
转自：http://blog.csdn.net/mango9126/article/details/72840897
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

算法

快速排序

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

  • 在java程序中使用c++ Dll

    我正在尝试使用System LoadLibrary 使用我用 C 编写的一个简单的 dll UseDllInJava java import com sun jna Library import com sun jna Native imp

  • 具有不同大小结构的结构数组的 malloc()

    如果每个结构都包含一个大小不同的字符串数组 那么如何正确地 malloc 一个结构数组 因此每个结构可能有不同的大小 并且不可能 realloc 结构体数量 sizeof 结构体名称 after malloc 初始大小 sizeof 结构名

  • 内联函数/方法

    声明 内联函数必须在调用之前定义 这个说法正确吗 EDIT 该问题最初是德语 内联功能穆森 弗 伊赫雷姆 奥夫鲁夫定义 sein 也许它对任何人都有帮助 是的 它是正确的 但只是部分正确 它可能正确地重新构建如下 内联函数必须在每个翻译单位

  • 将字节数组转换为托管结构

    更新 这个问题的答案帮助我编写了开源项目GitHub 上的 AlicanC 现代战争 2 工具 https github com AlicanC AlicanC s Modern Warfare 2 Tool 你可以看到我是如何阅读这些数据

  • 为什么大多数平台上没有“aligned_realloc”？

    MSVC有自己的非标准函数 aligned malloc aligned realloc and aligned free C 17和C11引入了 std aligned alloc 其结果可以是de分配有free or realloc B

  • C# 正则表达式用于查找 中具有特定结尾的链接

    我需要一个正则表达式模式来查找字符串 带有 HTML 代码 中的链接 以获取文件结尾如 gif 或 png 的链接 示例字符串 a href site com folder picture png target blank picture

  • 从 C 结构生成 C# 结构

    我有几十个 C 结构 我需要在 C 中使用它们 典型的 C 结构如下所示 typedef struct UM EVENT ULONG32 Id ULONG32 Orgin ULONG32 OperationType ULONG32 Size

  • 获取尚未实例化的类的函数句柄

    我对 C 相当陌生 我想做的事情可能看起来很复杂 首先 我想获取一些函数的句柄以便稍后执行它们 我知道我可以通过以下方式实现这一目标 List

  • 2D morton 码编码/解码 64 位

    如何将给定 x y 的莫顿代码 z 顺序 编码 解码为 32 位无符号整数 生成 64 位莫顿代码 反之亦然 我确实有 xy2d 和 d2xy 但仅适用于 16 位宽的坐标 产生 32 位莫顿数 在网上查了很多 但没有找到 请帮忙 如果您可

  • 默认析构函数做了多少事情

    C 类中的默认析构函数是否会自动删除代码中未显式分配的成员 例如 class C public C int arr 100 int main void C myC new C delete myC return 0 删除 myC 会自动释放

  • C++11 动态线程池

    最近 我一直在尝试寻找一个用于线程并发任务的库 理想情况下 是一个在线程上调用函数的简单接口 任何时候都有 n 个线程 有些线程比其他线程完成得更快 并且到达的时间不同 首先我尝试了 Rx 它在 C 中非常棒 我还研究了 Blocks 和

  • 如何随着分辨率的变化自动调整大小和调整表单控件

    我注意到某些应用程序会更改控件的位置以尽可能适应当前的分辨率 例如 如果窗口最大化 则控件的设置方式应使整个 GUI 看起来平衡 是否可以使用 C 在 Visual studio 2010 中制作或实现此功能 Use Dock http m

  • DataTable：通过 LINQ 或 LAMBDA 进行动态 Group By 表达式

    我有一个数据表 我想在其中对未指定数量的字段进行分组 发生这种情况的原因是用户可以选择他想要分组的字段 所以 实际上 我将选择推入列表中 在这个选择上 我必须对我的数据表进行分组 想象一下这段代码 VB 或 C 都一样 public voi

  • 如何引用解决方案之外的项目？

    我有一个 Visual Studio C 解决方案 其中包含一些项目 其中一个项目需要引用另一个不属于解决方案的项目 一开始我引用了dll

  • 为什么 Linux 对目录使用 getdents() 而不是 read()？

    我浏览 K R C 时注意到 为了读取目录中的条目 他们使用了 while read dp gt fd char dirbuf sizeof dirbuf sizeof dirbuf code Where dirbuf是系统特定的目录结构

  • C语言声明数组没有初始大小

    编写一个程序来操纵温度详细信息 如下所示 输入要计算的天数 主功能 输入摄氏度温度 输入功能 将温度从摄氏度转换为华氏度 独立功能 查找华氏度的平均温度 我怎样才能在没有数组初始大小的情况下制作这个程序 include

  • 为什么文件更新时“如果较新则复制”不复制文件？

    我在 Visual Studio Express 中有一个解决方案 如下所示 The LogicSchemaC 中的类 将在运行时解析指定的 XML 文件 以下是在main的方法Program cs LogicSchema ls new L

  • C++、三元运算符、std::cout

    如何使用 C 用三元运算符编写以下条件 int condition1 condition2 condition3 int double result int or double std cout lt lt condition1 resul

  • 带有私有设置器的 EFCore Base 实体模型属性 - 迁移奇怪的行为

    实体模型继承的类内的私有设置器似乎会导致 EFCore 迁移出现奇怪的问题 考虑以下示例 其中有多个类 Bar and Baz 继承自Foo 跑步时Add Migration多次命令 添加 删除private修饰符 生成的模式在多个方面都是

  • 如何使用 C# 以低分辨率形式提供高分辨率图像

    尝试使用 300dpi tif 图像在网络上显示 目前 当用户上传图像时 我正在动态创建缩略图 如果创建的页面引用宽度为 500x500px 的高分辨率图像 我可以使用相同的功能即时转换为 gif jpg 吗 将创建的 jpg 的即将分辨率

随机推荐

  • 打开VMware虚拟机时提示“内部错误”

    解决方法 输入命令行 services msc打开服务 将上述服务重启 可以正常进入虚拟机

  • 移动Web：媒体查询及手机端PC端识别

    媒体查询 响应式布局的核心 能够检测视口的宽度 然后编写差异化的 css 样式调整网页的布局方式 响应式布局原理 根据 UI 设计稿需求合理设置响应断点 配合媒体查询书写差异化CSS样式 响应断点是指媒体查询所采用的视口的宽度 作用 将屏幕

  • SAR: 1 4 https://www.vulnhub.com/entry/sar-1%2C425/

    SAR 1 About Release Back to the Top Name Sar 1 Date release 15 Feb 2020 Author Love Series Sar Download Back to the Top

  • 一种基于卷积神经网络的图像去雾研究-含matlab代码

    目录 一 绪论 二 去雾卷积网络 2 1 特征提取 2 2 多尺度映射 2 3 局部均值 2 4 非线性回归 三 实验与分析 四 Matlab代码获取 一 绪论 雾是一种常见的大气现象 空气中悬浮的水滴 灰尘 细沙或其他颗粒等都会引起成像清

  • SpringBoot 配置全局异常处理

    SpringBoot 项目pom xml 依赖配置文件

  • 数字化时代新经营模式千载难逢的翻身机会

    随着互联网的兴起 它对于线下实体商户的冲击早已不是一天两天了 网上店铺的崛起 吸引走了大部分流量 这对于靠流量吃饭的线下商户来说 是致命的打击 相关数据统计 这几年 随着网络购物越来越火热 越来越成为一种消费主流 线下实体商户的闭店率出现了

  • 迪文串口屏TTL与主控板RS232电平信号转换方案

    一 TTL和RS232简述 串口 COM口是指的物理接口形式 硬件 按位 bit 发送和接收字节 而TTL RS 232是指的电平标准 电信号 TTL和RS232不同在于 电平表示的逻辑含义不同 1 TTL 逻辑高电平 1 3 3V或5V

  • (转)工业机器人用什么语言编程的？

    机器人的开发语言一般为C C C Builder VB VC等语言 主要取决于执行机构 伺服系统 的开发语言 而机器人编程分为示教 动作级机器人编程语言 任务级编程语言三个级别 机器人编程语言分为专用操作语言 如VAL语言 AL语言 SLI

  • Dynamic Web project,Jsp可正常访问，servlet出现404，刷新出现Http500，解决方式

    新手建立首个Dynamic Web project Jsp可正常访问 servlet出现404 刷新出现Http500 解决方式如下 Tips 关于配置servlet到web xml Servlet class 为pakagename se

  • PyTorch 的 Autograd详解

    点击蓝字 关注视学算法 作者丨xiaopl 知乎 来源丨https zhuanlan zhihu com p 69294347 编辑丨极市平台 PyTorch 作为一个深度学习平台 在深度学习任务中比 NumPy 这个科学计算库强在哪里呢

  • Go语言学习9-结构体类型

    结构体类型 引言 1 结构体 1 1 类型表示法 1 2 值表示法 1 3 属性和基本操作 附录 引言 书接上篇 我们了解了Go语言的接口类型 现在介绍Go语言的结构体类型 主要如下 1 结构体 结构体类型既可以包含若干个命名元素 又称字段

  • React从入门到精通二

    React从入门到精通之购物车案例 1 购物车需求说明 使用到的data list 2 项目code 1 购物车需求说明 list data展示到列表中 每个item的通过 按钮来控制购买的数据量 删除按钮可以删除当前的item Total

  • Request+超详细代码+视图分析（获取值）

    Request 1 request对象和response对象的原理 1 request和response对象是由服务器创建的 我们来使用它们 2 request对象是来获取请求消息 response对象是来设置响应消息 2 request对

  • constrain用法_constrain是什么意思_constrain的用法

    constrain的音标 英 k n stre n 美 k n stre n constrain的用法 v 强迫 强制 迫使 限制 限定 约束 第三人称单数 constrains 现在分词 constraining 过去式 constrai

  • Numpy学习笔记

    基于Wes McKinney的Python for Data Analysis第四章NumPy Basics Arrays and Vectorized Computation整理代码得来 最近在自学Python 感觉还是要敲一下的 又懒得

  • ChatGPT的评估指标有哪些？微调与上下文学习是否存在相似性？

    NLP 分很多的任务 不同的任务有不同的指标来度量模型质量 比如AUC Precision Recall是分类模型的度量指标 ChatGPT可以看作一个生成式语言模型 简单说就是给它输入一段文字 它会输出另一段文字 当然输出和输入之间是有关

  • 关于ArithmeticException 异常捕获（double类型的数据除于0为什么是无穷大？）

    关于ArithmeticException 异常捕获 double类型的数据除于0为什么是无穷大 在做实验编写应用程序 从命令行中输入表示两个小数的参数的字符串 求它们的商 要求程序捕获NumberFormatException异常和Ari

  • 测试用例管理工具SynapseRT（jira插件）的具体使用（一）

    话说我们测试团队使用Zephyr进行测试用例管理一段时间后 得到大家的认可 反馈还不错 但我还是觉得它功能太单一 缺点较多 例如提供信息较少 无法记录和跟踪需求 管理人员无法直观了解测试进度等等 为了解决这些问题 我找到了SnapseRT插

  • 基于DVWA的文件上传漏洞测试

    目录 DVWA Low Medium DVWA Low DVWA Security的 low 级别可以直接上传 一句话 木马 1 1 编写测试木马 1 2 没有后缀过滤直接上传 1 3回显上传路径 直接访问即可 http localhost

  • 算法 - 快速排序（C#）

    csharp view plain copy print

热门标签