perl从sort到施瓦茨变换

这篇博文记录perl的排序算法,从sort的简单排序到简洁漂亮的施瓦茨变换.

sort基本用法sort自定义排序施瓦茨变换 谁的工资高优化的排序方式施瓦茨变换工资一样的员工年龄大的排前面施瓦茨变换实现多级排序

sort基本用法

语法 sort LIST

## sort 默认情况对文本字符按照字符顺序排序 ## 对字符串排序 my @namelist = qw/bob marry jack simon ann tiger/; print "sort namelist:", sort "@namelist"; ## sortedNameList: ann bob jack marry simon tiger ## 对字符串排序 my @sortedNumber = sort qw/11 33 21 2 1 54 43 3 222/; print "sortedNumber: @sortedNumber\n"; ## sortedNumber: 1 11 2 21 222 3 33 43 54

sort自定义排序

语法 sort BLOCK LIST

## 在block代码块中使用`<=>`(飞船操作符)返回一个编码值来指明排序的顺序 my @sortedNumber = sort { $a <=> $b } qw/11 33 21 2 1 54 43 3 222/; print "sortedNumber: @sortedNumber\n"; ## 输出 sortedNumber: 1 2 3 11 21 33 43 54 222 ## 如果要降序排序 修改代码块为{ $b <=> $a } ## 也可以 reverse @sortedNumber实现降序 对sort函数来说,BLOCK代码块的实现决定了排序结果是升序还是降序,$a <=> $b操作用于对数字的比较,跟如下代码一样if( $left < $right ) {return -1} elsif( $left == $right ) {return 0} else {return 1};飞船操作符不关心$a $b谁在左边谁在右边的问题,对于sort来说$a $b是每次需要比较的来自LIST中的两个元素;可以这样理解:$a的index总是比$b的index更小,所以用{ $a <=> $b }排序的结果是由小到大的升序LIST. 反之{ $b <=> $a }则为降序,不过为了使代码更可读,使用reverse对升序的LIST翻转获取降序LIST.

施瓦茨变换

谁的工资高

某公司有六个职员,老板需要这六个职员按工资排名的清单,下面用一份代码表示这个计算过程.

my @namelist = qw/bob marry jack simon ann tiger/; my @namelistBysalary = sort { asksalary($a) <=> asksalary($b) } @namelist; ## asksalary()是返回salary的子例程

思考: 当要比较bob和marry的工资时,通过asksalary("bob")获取bob的工资,asksalary("marry")获取marry的工资,然后比较;当要比较bob和jack的工资时,sort代码块又要执行一次asksalary("bob"),以此类推无疑是对资源的一种浪费,尤其是员工越来越多的时候.

优化的排序方式

使用一个中间数组保存每个人的工资,这样不必每次都去asksalary().

my @namelist = qw/bob marry jack simon ann tiger/; my @array_salary = map { [$_, asksalary($_)] ##返回一个数组引用 [name,salary] } @namelist; my @array_salary_sorted = sort { ## 通过工资对数组排序 $a->[1] <=> $b[1] } @array_salary; my @namelistBysalary = map { ## 从排序后的数组中取出的就是员工排名 $_->[0]; } @array_salary_sorted;

施瓦茨变换

那么将上一节中的代码组合到一起就是施瓦茨变换, 施瓦茨变换从右往左看.

my @namelist = qw/bob marry jack simon ann tiger/; ## 施瓦茨变换 my @namelistBysalary = map { $_->[0] } ##第三步 从排序后的LIST中取出name组成最后的list sort { $a->[1] <=> $b->[1] } ##第二步 sort对LIST排序,排序依据salary map [$_, asksalary($_)], @namelist ; ##第一步 map返回一个LIST,LIST中的元素是数组引用[ name,salary ] print "swc: @namelistBysalary\n";

工资一样的员工年龄大的排前面

## 施瓦茨变换 my @namelistBysalary = map { $_->[0] } ( ## 此小括号为增加可读性 sort { $a->[1] <=> $b->[1] or ## 工资一样的时候 $b->[2] <=> $a->[2] ## 年龄按照降序排 } ( map [$_, asksalary($_), askage($_)], @namelist ) ); print "swc: @namelistBysalary\n";

施瓦茨变换实现多级排序

工资也一样/年龄也一样/身高…/性别… 当排序的条件越来越多,匿名数组就不方便了,把数组改为hash更好用

## 施瓦茨变换多级排序 my @namelistBysalary = map { $_->{name} } ( ## 此小括号为增加可读性 sort { $a->{salary} <=> $b->{salary} or $b->{age} <=> $a->{age} or $b=>{height} <=> $b->{height} } ( ## 此小括号为增加可读性 map +{ ## 返回一个hash引用 name => $_, salary => asksalary($_), age => askage($_), height => askheight($_), }, @namelist ) ); print "swc: @namelistBysalary\n";