Tag Archives: 排序

Python Sort多值排序

假设使用lambda函数
s = sorted(s, key = lambda x: (x[1], x[2]))
如上所示，返回一个tuple，其中[0]是第1个排序key，[1]是第2个。[......]

Linux sort的四个小技巧

像排序这种事情，用C/C++可以写，但很麻烦，交给sort就好了，功能很强大的。

1、按照多个列排序（列间空格分开）：

测试数据：

先按照第1列排序，再第2列的命令：

2011-11-20补充：必须加-s选项，表示stable sort，即两列排序互相不打扰。
$ cat ./test
1       x
5       8
1       a

$ sort -s -k 1 -k 2 ./test
1       a
1       x
5      [......]

算法技术手册 – 排序 – 如何选择排序算法

实际上，没有绝对优秀的、应该始终采用的排序算法。

书上给出了一些选择不同排序算法的理由，写的非常好，抄录一下。

元素很少：插入排序
几乎有序：插入排序
关注最差情况：堆排序（牢记：堆排序的最差时间复杂度依然是O(nlogn)）
平均较好：快速排序
元素从密集范围取出：桶排序
代码量小：插入排序

书上也在不同应用环境：字符串、浮点、几乎有序等情况下进行了测试，有兴趣的可以去翻阅。[......]

算法技术手册 – 排序 – 桶排序/哈希排序/散列排序

1 Reply

在前面的计数排序中，我们已经领略到了如何用空间换时间的方法，找到一种线性时间复杂度O(N)的排序算法。

计数排序的缺点也是非常明显的：一旦数据范围[0,k)，中的k]相对于数据量N非常稀疏，计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

个人认为：桶排序 = 哈希排序 = 散列排序，基本思想是一样的。

于是桶排序/哈希排序应运而生，假设值域范围还是k，我们不去创建k个buckets，而是创建m个木桶，让N个元素通过哈系函数映射到这k个桶即可。这里还有一个[......]