首页 ›存档› 技术 › 查看内容

用菜鸟的思维学习算法 -- 马桶排序、冒泡排序和快速排序

2018-3-30 13:00 |来自: 互联网 552 0

摘要: 来自：反骨仔（二五仔） - 博客园链接：www.cnblogs.com/liqingwen/p/4994261.html（点击尾部阅读原文前往）已获转载授权目录马桶排序（令人作呕的排序）冒泡排序（面试都要问的算法）快速排序（见证亚当和 ...

来自：反骨仔（二五仔） - 博客园

链接：www.cnblogs.com/liqingwen/p/4994261.html（点击尾部阅读原文前往）

已获转载授权

马桶排序（令人作呕的排序）

一、场景：期末考试完了，老师要将同学们的分数从高到低排序。假设班上有 5 名同学，分别考了 5 分、3 分、5 分、2 分和 8 分【满分：10 分】，排序后的结果就是 8 5 5 3 2，现在，让我们先思考 10 分钟吧！

二、思路：

（1）先创建一个数组 int scores[11]，就有 scores[0]~scores[10] 共 11 个变量。我们用变量值为 0 表示没有人得到该分数，即 scores [0]=0 表示没有人得 0 分，scores [10]=0 表示没有人得 10 分，而 scores [8]=1 表示有一个人得到 8 分。

（2）第 1 个数为 5，所以在 scores[5]=0 的基础上 1，即 scores[5]=1 表示有 1 人得到 5 分

（3）第 2 个数为 3，所以在 scores[3]=0 的基础上 1，即 scores[3]=1 表示有 1 人得到 3 分

（4）第 3 个数为 5，所以在 scores[5]=1 的基础上 1，即 scores[5]=2 表示有 2 人得到 5 分

　　　　　　... ...

（5）依此类推，处理第 4 和第 5 个数，最终的结果图如下：

（6）我们发现，scores[0]~scores[10] 内对应的值就是 0~10 分中每个分数所出现的次数。现在，只需将结果打印即可，出现几次就打印机次。

我们暂且称它为“马桶排序”，这个算法就相当于有 11 个马桶，编号从 0~10。每出现一个数，就在对应编号的马桶中放一个旗子。

图：这里有 11 个马桶

三、思考：现在分别有 5 个人的名字和分数：小A 5、小二 3、小三 5、小妞2 和王大锤 8，请按照分数从高到低，输出他们的名字？

【特点】

假设需要排序的范围 0~20000000，则需要 new int[20000001]，非常浪费空间，即便只给 2 个数排序（1,19999999 ）;

如果排序的数是小数也不行，如：3.141 5926 5358 9793 2384 6264 3383 2795 0238；

这里使用 C# 给出简单的算法过程。

static void Main(string[] args)  
     {  
       var scores = new int[] { 5, 3, 5, 2, 8 };  
       var newScores = new int[9];  

       for (int i = 0; i

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：浅谈字符串匹配算法BF 算法及 KMP 算法下一篇：PID控制算法精华总结在过程控制中，按偏差的比例（P）、积分（I）和微分（D）进行控 ...

用菜鸟的思维学习算法 -- 马桶排序、冒泡排序和快速排序

目录

马桶排序（令人作呕的排序）

相关分类