c#实现最简洁的快速排序(你绝对可以看懂)
作者:colorfulCat 发布时间:2022-04-01 22:35:48
前言
算法对于程序员的重要性不言而喻,今天我和大家分享算法中的一个基础算法,快速排序。作为一名程序员,相信大家都不陌生,但是要大家徒手一次性写出来,我估计还是有难度的。那么废话不多少,我先简单减少一下概念。
快速排序算法说明:
原始数组L1,从中任意选择一个基准数F(一般选择第1个),小于F的数据放在F的左边记为数组minList,大于F的数据放在F的右边记为数组maxList。那么
L1=minList+F+maxList
然后对minList和maxList再做这样的操作,直到minList和maxList中的元素个数为1或者0的时候停止
一、C#网上目前最简洁的实现方式:
现在就是要进行算法的实现了,很明显,这里要用到一个叫递归的思想。我们知道编程语言知识工具,算法才是核心,但是不同的编程语言实现算法却有很大的不同(简洁程度)。目前网上对于c#的实现快速排序的方式有很多,简单查阅了一下,发现一般都要100行代码左右(c和c++的代码行数要少一些)。千找万找,终于找到了一个,贴出如下:
static void QuickSort(ref List<int> nums, int left, int right)
{
if (left < right)
{
int i = left;
int j = right;
int middle = nums[(left + right) / 2];
while (true)
{
while (i < right && nums[i] < middle) { i++; };
while (j > 0 && nums[j] > middle) { j--; };
if (i == j) break;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
if (nums[i] == nums[j]) j--;
}
QuickSort(ref nums, left, i);
QuickSort(ref nums, i + 1, right);
}
}
但是说真的,很难读懂,真要在考场上写出这个代码,难保能一次写对。
二、python的实现方式:
python我也有接触,所以当我用python写出这个算法的代码的时候,真的有种感觉,真是太TM简单了吧,有编程经验的同学应该也能看懂下面的python代码
def quicksort(array):
if len(array) < 2:
return array ------基线条件:为空或只包含一个元素的数组是“有序”的
else:
pivot = array[0] ------递归条件
less = [i for i in array[1:] if i <= pivot] ------由所有小于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] ------由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
短短几行代码,清晰明了。主要的代码就是数组可以直接相加运算:quicksort(less) + [pivot] + quicksort(greater)
三、C#自己实现最简易方式
那难道我们c#就只能写出难懂又多的代码才能实现吗?终于让我也找到了,下面贴出我自己写的c#代码:
public class Extend :List<int>
{
public static Extend operator +(Extend L1, Extend L2)
{
L1.AddRange(L2);
return L1;
}
}
static Extend QuickSort2(Extend nums)
{
if (nums.Count < 2)
{
return nums;
}
else
{
Extend minList = new Extend();//小于基准数的集合
Extend maxList = new Extend();//大于基准数的集合
int f = nums[0];
for (int i = 1; i < nums.Count; i++)
{
if (nums[i] <= f) minList.Add(nums[i]);
else maxList.Add(nums[i]);
}
return QuickSort2(minList) + new Extend() { f} + QuickSort2(maxList);//递归,并且使用+运算符
}
}
实际上就只有两步操作,就实现了和python一样的简洁!
第一:新建一个Extend 类继承于List<int>
第二:重写了+运算符
有同学对Extend类中的AddRange方法提出了内存上的质疑,我也进行了回复,算法是对时间复杂度的考察,也就是对过程的考察。内存消耗根据不同的代码肯定会有所不同,但是不影响算法。当然我也对Extend进行了改进,因为实际上最终的加法运算中,minList和maxList都只有一个元素,或者没有元素。
public class Extend :List<int>
{
private static Extend k = new Extend();
public static Extend operator +(Extend L1, Extend L2)
{
if (L1.Count == 1) k.Add(L1[0]);
if (L2.Count == 1) k.Add(L2[0]);
return k;
//L1.AddRange(L2);
//return L1;
}
}
其余的和python的代码基本一致,代码清晰明了。
据我观察,c#通过我这种方式实现的,目前独此一份,收好不谢!最后我还是要吐槽一句,怪不得python现在这么火,代码真的简单。但是最为程序员,我们始终要记住,语言只是工具,我们才是语言的主宰。了解代码背后的思想才是王道!
来源:https://www.cnblogs.com/pettyColorcat/p/10861302.html
猜你喜欢
- spring cloud 配置中心客户端启动先启动了配置中心,然后启动客户端,发现打印的日志是这样的2020-04-29 11:13:02.
- 小总结抛出异常:创建异常对象,封装异常信息然后通过throw将异常对象传递给调用者。不对异常进行处理只对异常进行抛出是非常不负责任的表现可以
- tokentoken的意思是“令牌”,是用户身份的验证方式,最简单的token组成:uid(用户唯一的身份标识)、time(当前时间的时间戳
- 这篇文章主要介绍了java接口私有方法实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可
- Java * 要想了解Java * ,首先要了解什么叫做代理,熟悉设计模式的朋友一定知道在Gof总结的23种设计模式中,有
- 环绕通知:它是spring框架为我们提供的一种可以在代码中手动控制增强部分什么时候执行的方式。问题:当我们配置了环绕通知之后,增强的代码执行
- 本文实例为大家分享了Android自定义View之组合控件,仿电商app顶部栏的相关代码,供大家参考,具体内容如下效果图:分析:左右两边可以
- 简介Exchanger是java 5引入的并发类,Exchanger顾名思义就是用来做交换的。这里主要是两个线程之间交换持有的对象。当Exc
- Spring中Profile对不同环境提供不同配置功能的支持,可以通过激活、指定参数等方式快速切换环境。文件名格式:application-
- 本文实例讲述了java用接口、多态、继承、类计算三角形和矩形周长及面积的方法。分享给大家供大家参考。具体如下:定义接口规范:/** * @
- Android的应用被限制为最多占用16m的内存,至少在T-Mobile G1上是这样的(当然现在已经有几百兆的内存可以用了——译者注)。它
- JWT可以理解为一个加密的字符串,里面由三部分组成:头部(Header)、负载(Payload)、签名(signature)由base64加
- Java 异步实现的几种方式1. jdk1.8之前的Futurejdk并发包里的Future代表了未来的某个结果,当我们向线程池中提交任务的
- 创建父级项目 只需保留pom.xml文件这里只需搭建一个微服务 其他操作并无<?xml version="1.0"
- 一.创建Spring boot项目,添加如下依赖<dependency> <gro
- 一、问题描述我们开发项目时,经常会和第三方接口打交道,有些第三方项目为了安全起见,会把项目部署在"内网"环境,不对外暴露
- 表述在一次服务更新后发现每天凌晨0点3秒服务准时挂,开始的时候认为是maven依赖中存在system.exit(3)类似这样的代码,但是我想
- 一. 假设需求场景在我们开发的过程中,经常出现两个对象存在一对多或多对一的关系。如何在程序在表明这两个对象的关系,以及如何利用这种关系优雅地
- 一、背景上一篇通过Java自带的JConsole来获取zookeeper状态。主要有几个不方便的地方,zk集群一般会部署3或者5台,在多个J
- 判断某字符串是否为空,为空的标准是str==null或str.length()==01.下面是StringUtils判断是否为空的示例:St