一道笔试题的解法和联想

简介:

(注:这里只是想通过排序算法来描述一下抽象的过程,所以大家不要太关注于数组的排序)

作者:方明

原题是这样的,请用C#编写一个可以对任意类型进行冒泡排序算法,我们先看一个整型的冒泡排序来了解一下冒泡排序:

 

整型冒泡排序

 

这个题其实考的重点并不在冒泡排序(当然不懂冒泡排序肯定不行),而是考一种抽象能力,对于冒泡排序来说,任意类型排序他们共同的东西就是冒泡排序的思想,而不同的部分在比较上,所以我们就要想一种方法将变化的部分和不变的部分隔离开,我们首先想到的方法是使用接口,下边是一种解法:

 

接口实现1

 

这个解法可以应对更多的类型排序,只要这些需要排序的类型都实现IArray接口就可以了,但是问题是如果这样,这个排序算法又不支持整型了,我们总不能为了这个排序算法重新封装一下整型吧。我们得继续寻找办法,于是我们想到了系统的一个接口IComparable,这个接口定义通用的比较方法,由值类型或类实现以创建类型特定的比较方法。系统自定义类型几乎都实现了这个接口,所以只要自定义类也实现这个接口就可以利用到这里了,代码如下:

 

接口实现2

 

现在基本符合题意了,但看起来好像还不是好的解决方案,因为每个类型都要实现IComparable仍然是个限制,那如何打破这个限制呢,仔细想想,我们想出另外一个解决方案,就是想办法把比较方式封装起来,然后调用排序函数时传进来不就成了么。

 

接口实现3

 

大家可能觉得这个和上一个方案很象阿,不都要实现一个接口么,其实后一个方案中的最大优点在于你自定义类不用继承任何接口了,我们想一下,为了让某个类型支持这个冒泡排序而去实现一个接口是很牵强的。.net对数组,集合等的排序就是使用这个方法来做的,大家可以研究一下Array类中的静态方法public static void Sort(Array array, IComparer comparer);。那这个是不是最好的解决方案呢,我们本着不撞南墙不回头的原则继续前进,这个接口好像用委托也可以实现吧,那写个版本先:

 

委托实现

 

似乎也没有什么改进,还要写多写一个方法,但是这个委托版本已经基本接近我们的答案了,下面我们使用Lambda表达式来实现我认为的最优的答案(这个答案中需要大家了解Lambda表达式,范型以及Func委托):

 

Lambda表达式实现

 

ps:有网友问,不同类型排序怎么办,我觉得一样是需要把比较的方式和排序算法本身分离开来,我写了个简单例子供参考

 

任意类型排序


本文转自 你听海是不是在笑 博客园博客,原文链接:http://www.cnblogs.com/nuaalfm/archive/2008/08/23/1274868.html  ,如需转载请自行联系原作者
相关文章
|
存储 测试技术
(笔试)华为2021秋招面试真题!(内含详细解题思路)
<p>  前言:</p> <p>  文章内容主要介绍了华为2021秋招笔试题(小结),小编觉得挺不错的,现在特意在此分享给大家,也给大家做个参考。(部分代码,用图片的方式呈现出来,方便各位收藏与很好的观看)</p> <p>  内容如下:</p> <p>  一、全量字符集与已占用字符集</p> <p>  输入描述:</p>
981 0
|
2月前
acwing 110 抓住那头牛
acwing 110 抓住那头牛
10 0
|
7月前
|
存储 人工智能 算法
大数乘法的几种算法分析及比较(2014腾讯南京笔试题)
大数乘法的几种算法分析及比较(2014腾讯南京笔试题)
|
7月前
|
C++ 存储 Serverless
力扣C++|一题多解之数学题专场(2)
力扣C++|一题多解之数学题专场(2)
50 0
力扣C++|一题多解之数学题专场(2)
|
7月前
|
C++ 存储
力扣C++|一题多解之数学题专场(1)
力扣C++|一题多解之数学题专场(1)
52 0
力扣C++|一题多解之数学题专场(1)
|
7月前
|
机器学习/深度学习
蓝桥杯-2/14天-完全平方数【另类思路】
蓝桥杯-2/14天-完全平方数【另类思路】
|
人工智能 算法 机器人
迷宫问题(C语言实现)(牛客网百度笔试真题)
迷宫问题(C语言实现)(牛客网百度笔试真题)
245 0
|
算法 C++
【每日算法Day 95】美团笔试题:四面体方案个数
【每日算法Day 95】美团笔试题:四面体方案个数
|
算法 C++
【每日算法Day 103】老题新做,几乎不会有人想到的解法,它来了
【每日算法Day 103】老题新做,几乎不会有人想到的解法,它来了
104 0
|
机器学习/深度学习
走进递归经典——青蛙跳台阶问题详解
描述👏 继汉诺塔问题之后,接下来就是青蛙跳台阶问题:​说一只青蛙一次可以跳上1级,也可以跳上2级,求该青蛙跳上一个n级的台阶总共有多少种跳法。刚开始感觉像是在算阶乘,考虑先后次序不同算不同的结果嘛;看完才发现我格局低咯,这题其实蛮有意思。
走进递归经典——青蛙跳台阶问题详解