VBA编程常用的排序算法之计数排序

2015-02-28

七月的风,八月的雨,卑微的我喜欢遥远的你……



1,

大家好,我是看见星光。

长期关注我们EH公众号的朋友都知道,老祝家有个丫头在统计局上班,她曾经眼睛都不眨的对我说过这样一句话:

排序是数据分析与处理过程中最常见也是最重要的问题之一,搞定排序可以提升工作效率3.485626%……

看在老祝爱发红包的份上,我当然对她这话发自肺腑的相信,所以曾发过两篇推文:



Excel自带的排序功能确实已经足够强大,既能单列排序也能多列排序,既能按数值排序还能按颜色排序,甚至支持自定义规则排序,而且排序效率也非常优秀……

不过,有些情况,就不适合使用工作表排序方案了。比如……

大小不一合并单元格的情况下它会罢工。

复杂数据结构下的排序它会歇菜。

另外,毕竟这家伙是基于单元格对象的,如果咱们需要排序的数据并非存放在单元格中,它就更爱莫能助了。

比如VBA数组内部的元素如何排序?

恩,很遗憾,VBA数组并没有像其它语言那样自带排序的属性方法。

当此危难时刻,说不得咱就得自力更生,掌握点传说中编程的核心科技……排序算法了。

排序算法有很多,但复杂的咱们没闲心管,少用的我们也懒得理,所以就分享三个最常用最简单的:计数排序,冒泡排序,快速排序。


2,

先说计数排序。

为什么先说它呢?不是它长的帅,理智+帅气如我不会犯如此幼稚的错误,原因只有一个——这货最简单。

什么是计数排序呢?简单的说,就是利用数组下标来确定元素的正确位置,在数组中记录元素出现的次数,最后得出有序数据。

举个例子还是。

如下图所示,为某公司几位拥有百万年薪……小职员的考核得分表,得分范围是1~10之间的整数。

现在,我们需要把“看见星光”……也就是理智+帅气的在下了……的得分按升序排列,结果如下。

……

首先,我们根据得分的范围,也就是最低分1,最高分10,建立一个数组。

Redim r(1 to 10)

如此一来,我们声明了一个数组r,里面包含10个元素。数组是有序的元素集合,因此第一个元素就是r(1),第2个元素就是r(2)……其余以此类推。

目前这个数组是空的,刚建国,一穷二白,啥都没有。

然后我们遍历数据,按号入座,把每个得分按照对应的数组索引号计入数组,并累加出现次数。

比如说7,那就是r(7)=r(7)+1

当7第一次出现时,r(7)=1

当7第二次出现时,r(7)就等于1+1,也就是2……对吧?

于是代码如下

    For Each rng In [b2:g2]        n = rng.Value        r(n) = r(n) + 1    Next

数据遍历完成后,数组的情况就成了下图这样。

1、4、6、10各出现了一次,计数为1,7出现了两次,计数为2.

……

最后,我们根据数组记录的次数,依次把数据算出就OK了。

r(1)存在1次,说明数据源出现过一个1,于是我们得出一个1

r(2)为空,不管它

r(3)为空,不管它

r(4)存在1次,说明数据源出现了一个4,于是我们得出一个4

r(5)为空,不管它

r(6)存在1次,我们得出一个6

r(7)存在2次,说明数据源出现了两个7,于是我们得出7和7

……

因此最后得出升序排序结果1、4、6、7、7、10

整个过程的完整代码如下:

Sub VBACountingSort()    Dim aData, aResult, r    Dim i&, j&, n&, k&    Dim lngMin&, lngMax&    aData = Range("b2:g2").Value    '数据源装入数组adata    lngMax = Application.Max(aData)    '数据中的最小值    lngMin = Application.Min(aData)    '数据中的最大值    ReDim r(lngMin To lngMax)    '建立一个数组,范围是最小值到最大值之间,例如1 to 10    ReDim aResult(1 To UBound(aData)*UBound(aData,2), 1 To 1)    '结果数组    For i = 1 To UBound(aData, 2)    '遍历数据,按照索引号定位数据在数组r的正确位置,并累计出现次数        n = aData(1, i)        r(n) = r(n) + 1    Next    For i = lngMin To lngMax    '正序遍历数组,也就是从小往大取值        If r(i) > 0 Then        '如果指定数组下标内有数据            For j = 1 To r(i)            '按出现次数提取数据                k = k + 1                aResult(k, 1) = i                '数据写入结果数组            Next        End If    Next    Range("j1").Resize(k, 1) = aResult    '排序后的数据写入工作表End Sub


3,
简单说一下计数代码的扩展应用。
我们曾经使用计数排序搭配字典,实现过自定义规则排序,参考链接:

然后依然使用第一张图的数据为例,假设需要提取每个人前三名的成绩明细,结果如下图所示。你要不要动手写写代码?

4,
计数排序有以下两个局限点:
1),仅限于整数。
换个带小数点的,比如圆周率3.1415926,如果不变通的话,在数组中,按数组下标或者说索引定位,它就无处安放了。
所以,计数排序在实际应用中特别适合日期排序,毕竟在Excel中日期都是整数。
那么是不是说带小数的数值它就无能为力了呢?
比如下图所示的考试成绩表,可能包含84.5这样的小数,有几万条,能否使用计数排序?
其实是可以的。
嗯?前面不是说?
么么哒,我前面只是说如果不变通的话,带小数点的数值,计数算法它不行……
既然计数排序只能算整数,那你把小数转化成整数不就是了?84.5乘以10不就成了整数845了吗?
把数值全部统一放大十倍,也就把小数都变成了整数,计数排序后,从数组中取值时再除以10还原不就OK了??
做人不要太死板,对不对?
2),整数的跨度范围不宜过大
比如说,三个数排序,分别是1、100000、100000000,跨度范围是1到1亿之间,尽管它们是整数,但也不适合计数排序,时间和空间的复杂度都渣的一匹,大部分人的电脑估计连声明数组这步都会被警告内存不足……
那么此时我们应该怎么办呢?
如下图酱紫的,假设需要提取每个人前三收入的金额数据,怎么办?


……
关注我们,下期再贱。

相关文章

这些奇怪的排序算法,你没见过吧?

2015-03-17
编译: 伯乐在线 - 孙腾浩如有好文章投稿,请点击 → 这里了解详情【伯乐在线/算法爱好者 导读】:如果有人问你哪种排序算法最奇怪...

排序算法一览(上):交换类、选择类和插入类排序

2015-03-08
(点击尾部阅读原文前往)最近在复习常用排序算法发现了下面这个罪恶的排序方法列表页面,我被那些有趣的排序方法诱惑了,就把...

排序算法:Heap Sort 堆排序与 Top K 问题

2015-03-06
如果使用之前介绍的传统排序算法,先对N个元素进行全排序然后再取前K个元素,计算代价会变的非常高昂.因为我们实际上只需要...

秒懂排序算法

2015-03-06
cnblogs.com/guoyaohua0、排序算法说明0.1 排序的定义对一序列对象根据某个关键字进行排序.0.2 术语说明稳定:如果a原本在b前...

十大经典排序算法大梳理 (动图+代码)

2015-03-05
以前也零零碎碎发过一些排序算法,但排版都不太好,这次重新整理一次,排序算法是数据结构的重要部分,面试必问,系统地学习很...

图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序

2015-03-05
(点击尾部阅读原文前往)已获转载授权用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示.其实算法还是挺有趣的...

排序算法的彩色可视化,一目了然

2015-03-04
种排序算法,它们的速度快慢,一目了然.从左到右,从上到下,视频中的各算法如下:选择排序、希尔排序、插入排序;归并排序、...

排序算法

2015-03-03
稳定:相同元素排序后相对位置不变选择排序选择排序(Selection-sort)是一种简单直观的排序算法.它的工作原理:首先在未排序序...

排序算法总结(4):希尔排序

2015-03-02
它是直接插入排序算法的一种威力加强版.该方法因DL.Shell于1959年提出而得名.希尔排序的基本思想是:把记录按步长 gap 分组,...

图解排序算法(2):希尔排序

2015-03-02
于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序...

随机推荐

百万级数据导出,PHP是如何处理的!!

2020-09-09
4、编程语言PHP.技术难点:1、数据太大,对服务器配置要求较高,导出过程中涉及数据的处理(例如各种ID转换名称等操作,我们...

PHP编程语言常用的安全加固方法

2020-09-08
PHP即“超文本预处理器”,是一种通用开源脚本语言.PHP是在服务器端执行的脚本语言,其易于学习,使用广泛,主要适用于Web...

如何搭建Tik Tok环境(适用IOS保姆教程)

2020-08-30
//whoer.net检测环境是否伪装成功,伪装度能到90%以上就可以也可以到en.ipip.net查看下你的IP地址和定位经纬度,时区可以根据...

(实用篇)php注册和登录界面的实现案例

2020-06-22
login.php登录界面对应后台文件"."window.alert"."("."\""."请填写正确的信息!"."\"".")".";".""; echo"...

2015 年最好的 PHP 框架调查统计

2020-04-26
一个月前,我们就开始了一年一度SitePoint框架人气调查.现在月份已经到期, 这需要时间来看看结果. 共收到的回应是7800+个(...

内网渗透技术-零基础方向

2020-03-20
1、php脚本文件下载2、ftp文件下载>**windows下**>ftp下载是需要交互,但是也可以这样去执行下载open ...

Asproex(阿波罗)发展历程,心之所向,MOON之所及

2020-01-19

免费送书 | 《大话数据结构》

2015-02-17
多数前端程序员都觉得:数据结构好枯燥,算法太复杂.今天送出这本书 ——《 大话数据结构 》,作者尝试用轻松的文字和形象的图...

哈希表哪家强?几大编程语言吵起来了!

2015-02-02
哈希表华山论剑比特宇宙编程语言联合委员会准备举办一次大会,主题为哈希表,给各大编程语言帝国都发去了邀请函.很快就到了大...

小事 | 除死无大事

2015-01-10
Micromedia 多媒体制作软件制作的电子多媒体制品很像.电子书内容是黄金时代.有图案的背景.按空格可以翻页.同时有音乐.好...