Chinaunix

标题: sort的排序流程 [打印本页]

作者: ywlscpl 时间: 2010-08-26 05:24
标题: sort的排序流程
本帖最后由 ywlscpl 于 2010-08-26 09:34 编辑

一家之言，欢迎探讨。

关于sort的使用，最常用的-k参数的使用，指定几个-k参数，就是指定几个排序关键域，且按顺序依次为第1、第2...关键域。
man sort对-k是这么解释的:

-k, --key=POS1[,POS2]
start a key at POS1, end it at POS2 (origin 1)

如果不是很明白，可以这样理解：
1、-k2,3，表示关键域是从第2列到第3列
2、总列数为m列时，sort -k2 等价于 sort -k2,m
关键对-k2,m的理解，应该是“从第2列起到第m列止的字符串”，对于-k2,3来说，关键域就是第2列到第3列止的字符串。

明确概念后，下面讲讲sort的排序流程。
PS:翻到很久以前的一个帖子
http://bbs.chinaunix.net/viewthr ... &ordertype=0&page=1该贴所问的“为什么已经用-k3n,3指定只用第三个域进行排序，sort仍然对第四个域进行了排序？”让我有了弄清sort排序机制的念头。

sort -k参数的排序流程，个人理解，欢迎讨论：
1、针对每个-k参数指定的排序关键域，依次作为第1、第2、第n关键域进行排序
2、针对这n个关键域的排序后的结果中，对于这n个关键域都相同的行，sort再对这些行进行一次默认resort（未resort前是以原始顺序排序的）。
若指定了-s参数（GNU sort），resort不会进行。

-s, --stable
stabilize sort by disabling last-resort comparison

依次解析各个例子：
例子1、可以看到针对关键域3进行排序后，不会按原始顺序输出，因为sort又再次进行了resort

[root@Mylinux tmp]# cat file3
uucp:5:5:UUCP administrator:/usr/lib/uucp:
uucp:6:2:UUCP administrator:/usr/lib/uucp:
uucp:5:3:UUCP administrator:/usr/lib/uucp:
uucp:6:1:UUCP administrator:/usr/lib/uucp:
[root@Mylinux tmp]# sort -t: -k3,3n file3
uucp:5:3:UUCP administrator:/usr/lib/uucp:
uucp:5:5:UUCP administrator:/usr/lib/uucp:
uucp:6:1:UUCP administrator:/usr/lib/uucp:
uucp:6:2:UUCP administrator:/usr/lib/uucp:

等价的awk模拟sort排序流程(-k2,2作用就是模拟sort的resort)

[root@Mylinux tmp]# awk -F: -v OFS=# '{print $3,$0}' file3
5#uucp:5:5:UUCP administrator:/usr/lib/uucp:
6#uucp:6:2:UUCP administrator:/usr/lib/uucp:
5#uucp:x:5:3:UUCP administrator:/usr/lib/uucp:
6#uucp:x:6:1:UUCP administrator:/usr/lib/uucp:
[root@Mylinux tmp]# awk -F: -v OFS=# '{print $3,$0}' file3 |sort -t# -k1,1n -k2,2
5#uucp:x:5:3:UUCP administrator:/usr/lib/uucp:
5#uucp:x:5:5:UUCP administrator:/usr/lib/uucp:
6#uucp:x:6:1:UUCP administrator:/usr/lib/uucp:
6#uucp:x:6:2:UUCP administrator:/usr/lib/uucp:
[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file3 | sort -t# -k1,1 -k2,2 | awk -F# '{print $2}'
uucp:x:5:3:UUCP administrator:/usr/lib/uucp:
uucp:x:5:5:UUCP administrator:/usr/lib/uucp:
uucp:x:6:1:UUCP administrator:/usr/lib/uucp:
uucp:x:6:2:UUCP administrator:/usr/lib/uucp:

例子2、
sort -k2等价于sort -k2,4，排序关键域为第2至第4域为止的字符串

[root@Mylinux tmp]# cat file
a 2 7 1
b 2 4 5
c 9 1 6
d 6 9 7
e 1 8 5
f 8 1 3
g 4 4 3
h 6 3 4
[root@Mylinux tmp]# sort -k2 file
e 1 8 5
b 2 4 5
a 2 7 1
g 4 4 3
h 6 3 4
d 6 9 7
f 8 1 3
c 9 1 6

等价awk模拟过程

[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file
2 7 1#a 2 7 1
2 4 5#b 2 4 5
9 1 6#c 9 1 6
6 9 7#d 6 9 7
1 8 5#e 1 8 5
8 1 3#f 8 1 3
4 4 3#g 4 4 3
6 3 4#h 6 3 4
[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file | sort -t# -k1,1 -k2,2
1 8 5#e 1 8 5
2 4 5#b 2 4 5
2 7 1#a 2 7 1
4 4 3#g 4 4 3
6 3 4#h 6 3 4
6 9 7#d 6 9 7
8 1 3#f 8 1 3
9 1 6#c 9 1 6
[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file | sort -t# -k1,1 -k2,2 | awk -F# '{print $2}'
e 1 8 5
b 2 4 5
a 2 7 1
g 4 4 3
h 6 3 4
d 6 9 7
f 8 1 3
c 9 1 6

例子3、
sort -k2n 等价于sort -k2,4n，可以看到排序结果跟sort -k2不一样了，关键在于前面所说的：
对-k2,m的理解，应该是“从第2列起到第m列止的字符串”，而加了n参数后，导致对这一关键域的排序结果变了

[root@Mylinux tmp]# cat file
a 2 7 1
b 2 4 5
c 9 1 6
d 6 9 7
e 1 8 5
f 8 1 3
g 4 4 3
h 6 3 4
[root@Mylinux tmp]# sort -k2n file
e 1 8 5
a 2 7 1
b 2 4 5
g 4 4 3
d 6 9 7
h 6 3 4
f 8 1 3
c 9 1 6

awk模拟sort流程

[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file
2 7 1#a 2 7 1
2 4 5#b 2 4 5
9 1 6#c 9 1 6
6 9 7#d 6 9 7
1 8 5#e 1 8 5
8 1 3#f 8 1 3
4 4 3#g 4 4 3
6 3 4#h 6 3 4
[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file | sort -t# -k1,1n -k2,2
1 8 5#e 1 8 5
2 7 1#a 2 7 1
2 4 5#b 2 4 5
4 4 3#g 4 4 3
6 9 7#d 6 9 7
6 3 4#h 6 3 4
8 1 3#f 8 1 3
9 1 6#c 9 1 6
[root@Mylinux tmp]# awk -v OFS=# '{print $2" "$3" "$4,$0}' file | sort -t# -k1,1n -k2,2 | awk -F# '{print $2}'
e 1 8 5
a 2 7 1
b 2 4 5
g 4 4 3
d 6 9 7
h 6 3 4
f 8 1 3
c 9 1 6

例4、
对此贴的例子进行验证http://bbs2.chinaunix.net/viewth ... 73591&extra=&page=1

>sort -t, -k2 -k4 file
c2,7,3,13
c1,7,6,24
b2,8,1,17
b1,8,7,15
a1,9,2,21
a2,9,4,11
>sort -t, -k2,2 -k4,4 file
c2,7,3,13
c1,7,6,24
b1,8,7,15
b2,8,1,17
a2,9,4,11
a1,9,2,21

sort -k2 -k4等价于sort -k2,4 -k4,4

[root@Mylinux tmp]# sort -t, -k2 -k4 file4
c2,7,3,13
c1,7,6,24
b2,8,1,17
b1,8,7,15
a1,9,2,21
a2,9,4,11
[root@Mylinux tmp]# awk -F, -v OFS=# '{print $2","$3","$4,$4,$0}' file4 | sort -t# -k1,1 -k2,2 -k3,3 | awk -F# '{print $NF}'
c2,7,3,13
c1,7,6,24
b2,8,1,17
b1,8,7,15
a1,9,2,21
a2,9,4,11

[root@Mylinux tmp]# sort -t, -k2,2 -k4,4 file4
c2,7,3,13
c1,7,6,24
b1,8,7,15
b2,8,1,17
a2,9,4,11
a1,9,2,21
[root@Mylinux tmp]# awk -F, -v OFS=# '{print $2,$4,$0}' file4 | sort -t# -k1,1 -k2,2 -k3,3 | awk -F# '{print $NF}'
c2,7,3,13
c1,7,6,24
b1,8,7,15
b2,8,1,17
a2,9,4,11
a1,9,2,21

作者: bbgg1983 时间: 2010-08-26 09:04
大家早，学习了

作者: jiwang1980 时间: 2010-08-26 09:18
回复 1# ywlscpl

先顶下，再慢慢学习

作者: haokanwk 时间: 2010-08-26 09:19
先收藏，以后再看!

作者: 渣渣鸟 时间: 2010-08-26 09:25
excellent

作者: bbgg1983 时间: 2010-08-26 09:33
例4貌似有点不太对？

sort -k2 -k4等价于sort -k2,4 -k4,4

复制代码

这个不等价吧？

作者: ashlv 时间: 2010-08-26 09:34
沙发

作者: 好看的附件 时间: 2010-08-26 09:42
学习，LZ好早

作者: 709101040516 时间: 2010-08-26 09:45

收下了。。

作者: ywlscpl 时间: 2010-08-26 09:46
回复 6# bbgg1983

sort -k2 -k4等价于sort -k2,4 -k4,4

第1排序关键域：第2至4列的字符串
第2关键域：第4列

其实第2关键域是多余的，因为第2关键域-k2,4相同的行，第2关键域肯定相同-k4,4

我只所以验证这个例子，是为了说明-k参数的使用，都可以套用这个流程。

作者: wild_li 时间: 2010-08-26 09:51
关注

作者: wild_li 时间: 2010-08-26 09:56
sort排序的时候,特别是数字,有没有办法按数字的大小排,不要把1000排在了2的前面

作者: bbgg1983 时间: 2010-08-26 10:03
回复 10# ywlscpl

不好意思，看花眼了，我看成：
sort -k2 -k4等价于sort -k2,2 -k4,4

作者: BangBull 时间: 2010-08-26 10:16

好文，正好 sort 还不大熟

作者: blackold 时间: 2010-08-26 10:59
回复 10# ywlscpl

要“精通”sort不容易。

我觉得不能简单地认为 -k1 -k4中的-k4是多余的。这要看具体要进行什么比较，进行数值排序时就有区别：

$ sort -n -t \ -k1,4 -k4,4 urfile
2 110 213 40
8 56 32 24
60 3 98 1
60 208 20 9
60 208 20 119
60 53 37 128
60 208 103 192
60 208 0 224
131 9 124 72

$ sort -n -t \ -k1,4 urfile
2 110 213 40
8 56 32 24
60 208 0 224
60 208 103 192
60 208 20 119
60 208 20 9
60 3 98 1
60 53 37 128
131 9 124 72

作者: blackold 时间: 2010-08-26 11:01
回复 12# wild_li

使用数值排序就可以了。-n

作者: xiaopan3322 时间: 2010-08-26 11:30

沙发
ashlv 发表于 2010-08-26 09:34

这也算沙发？哈哈

作者: 好看的附件 时间: 2010-08-26 11:34
回复 17# xiaopan3322

这个情况应该是在点下鼠标的瞬间，同时多个alt-s,shift-enter操作发生的

作者: bingling512 时间: 2013-09-13 09:20
例子很丰富

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)