基本上所有正而八经的算法教材都会解释像 快速排序 quicksort 和 堆排序 heapsort 这样的排序算法有多快，但并不需要复杂的数学就能证明你可以逐渐趋近的速度有多快。关于标记的一个严肃说明：大多数计算机专业的科学家使用大写字母 O 标记来指代“趋近，直到到达一个常数比例因子”，这与数学专业所指代的意义是有所区别的。这里我使用的大 O 标记的含义与计算机教材所指相同，但至少不会和其他数学符号混用。基于比较的排序先来看个特例，即每次比较两个值大小的算法（快速排序、堆排序，及其它通用排序算法）。这种思想后续可以扩展至所有排序算法。一个简单的最差情况下的计数角度假设有 4 个互不相等的数，且顺序随机，那么，可以通过只比较一对数字完成排序吗？显然不能，证明如下：根据定义，要对该数组排序，需要按照某种顺序重新排列数字。换句话说，你需要知道用哪种排列方式？有多少种可能的排列？第一个数字可以放在四个位置中的任意一个，第二个数字可以放在剩下三个位置中的任意一个，第三个数字可以放在剩下两个位置中的任意一个，最后一个数字只有剩下的一个位置可选。这样，共有 4×3×2×1=4!=24 种排列可供选择。通过一次比较大小，只能产生两种可能的结果。如果列出所有的排列，那么“从小到大”排序对应的可能是第 8 种排列，按“从大到小”排序对应的可能是第 24 种排列，但无法知道什么时候需要的是其它 22 种排列。通过 2 次比较，可以得到 2×2=4 种可能的结果，这仍然不够。只要比较的次数少于 5（对应 2 5 = 32 种输出），就无法完成 4 个随机次序的数字的排序。如果 W(N) 是最差情况下对 N 个不同元素进行排序所需要的比较次数，那么，两边取以 2 为底的对数，得：N! 的增长近似于 N N （参阅 Stirling 公式），那么，这就是最差情况下从输出计数的角度得出的 O(N log N) 上限。从信息论角度的平均状态的例子使用一些信息论知识，就可以从上面的讨论中得到一个更有力的结论。下面，使用排序算法作为信息传输的编码器：任取一个数，比如 15从 4 个数字的排列列表中查找第 15 种排列对这种排列运行排序算法，记录所有的“大”、“小”比较结果用二进制编码发送比较结果接收端重新逐步执行发送端的排序算法，需要的话可以引用发送端的比较结果现在接收端就可以知道发送端如何重新排列数字以按照需要排序，接收端可以对排列进行逆算，得到 4 个数字的初始顺序接收端在排列表中检索发送端的原始排列，指出发送端发送的是 15确实，这有点奇怪，但确实可以。这意味着排序算法遵循着与编码方案相同的定律，包括理论所证明的不存在通用的数据压缩算法。算法中每次比较发送 1 比特的比较结果编码数据，根据信息论，比较的次数至少是能表示所有数据的二进制位数。更技术语言点，平均所需的最小比较次数是输入数据的香农熵，以比特为单位。熵是衡量信息等不可预测量的数学度量。包含 N 个元素的数组，元素次序随机且无偏时的熵最大，其值为 log 2​ N! 个比特。这证明 O(N log N) 是一个基于比较的对任意输入排序的最优平均值。以上都是理论说法，那么实际的排序算法如何做比较的呢？下面是一个数组排序所需比较次数均值的图。我比较的是理论值与快速排序及 Ford-Johnson 合并插入排序 的表现。后者设计目的就是最小化比较次数（整体上没比快速排序快多少，因为生活中相对于最大限度减少比较次数，还有更重要的事情）。又因为 合并插入排序 merge-insertion sort 是在 1959 年提出的，它一直在调整，以减少了一些比较次数，但图示说明，它基本上达到了最优状态。一点点理论导出这么实用的结论，这感觉真棒！小结证明了：如果数组可以是任意顺序，在最坏情况下至少需要 O(N log N) 次比较。数组的平均比较次数最少是数组的熵，对随机输入而言，其值是 O(N log N) 。注意，第 2 个结论允许基于比较的算法优于 O(N log N)，前提是输入是低熵的（换言之，是部分可预测的）。如果输入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在确定一个位之前，其输入是有序的，插入排序性能接近 O(N)。在最差情况下，以上算法的性能表现都不超出 O(N log N)。一般排序算法基于比较的排序在实践中是个有趣的特例，但从理论上讲，计算机的 CMP 指令与其它指令相比，并没有什么特别之处。在下面两条的基础上，前面两种情形都可以扩展至任意排序算法：大多数计算机指令有多于两个的输出，但输出的数量仍然是有限的。一条指令有限的输出意味着一条指令只能处理有限的熵。这给出了 O(N log N) 对应的指令下限。任何物理上可实现的计算机都只能在给定时间内执行有限数量的指令，所以算法的执行时间也有对应 O(N log N) 的下限。什么是更快的算法？一般意义上的 O(N log N) 下限，放在实践中来看，如果听人说到任何更快的算法，你要知道，它肯定以某种方式“作弊”了，其中肯定有圈套，即它不是一个可以处理任意大数组的通用排序算法。可能它是一个有用的算法，但最好看明白它字里行间隐含的东西。一个广为人知的例子是 基数排序 radix sort 算法，它经常被称为 O(N) 排序算法，但它只能处理所有数字都能放入 k 比特的情况，所以实际上它的性能是 O(kN)。什么意思呢？假如你用的 8 位计算机，那么 8 个二进制位可以表示 2 8=256 个不同的数字，如果数组有上千个数字，那么其中必有重复。对有些应用而言这是可以的，但对有些应用就必须用 16 个二进制位来表示，16 个二进制位可以表示 2 16=65,536 个不同的数字。32 个二进制位可以表示 2 32=4,294,967,296 不同的数字。随着数组长度的增长，所需要的二进制位数也在增长。要表示 N 个不同的数字，需要 k ≥ log 2​ N 个二进制位。所以，只有允许数组中存在重复的数字时， O(kN) 才优于 O(N log N)。一般意义上输入数据的 O(N log N) 的性能已经说明了全部问题。这个讨论不那么有趣因为很少需要在 32 位计算机上对几十亿整数进行排序，如果有谁的需求超出了 64 位计算机的极限，他一定没有告诉别人。via: https://theartofmachinery.com/2019/01/05/sorting_is_nlogn.html作者：Simon Arneaud 选题：lujun9972 译者：silentdawn-zz 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出
在 Linux、BSD 或 Mac 的终端中使用 sort 命令，按自己的需求重新整理数据。如果你曾经用过数据表应用程序，你就会知道可以按列的内容对行进行排序。例如，如果你有一个费用列表，你可能希望对它们进行按日期或价格升序抑或按类别进行排序。如果你熟悉终端的使用，你不会仅为了排序文本数据就去使用庞大的办公软件。这正是 sort) 命令的用处。安装你不必安装 sort ，因为它向来都包含在 POSIX 系统里。在大多数 Linux 系统中，sort 命令来自 GNU 组织打包的实用工具集合中。在其他的 POSIX 系统中，像 BSD 和 Mac，默认的 sort 命令不是 GNU 提供的，所以有一些选项可能不一样。本文中我尽量对 GNU 和 BSD 两者的实现都进行说明。按字母顺序排列行sort 命令默认会读取文件每行的第一个字符并对每行按字母升序排序后输出。两行中的第一个字符相同的情况下，对下一个字符进行对比。例如：$ cat distro.list Slackware Fedora Red Hat Enterprise Linux Ubuntu Arch 1337 Mint Mageia Debian $ sort distro.list 1337 Arch Debian Fedora Mageia Mint Red Hat Enterprise Linux Slackware Ubuntu使用 sort 不会改变原文件。sort 仅起到过滤的作用，所以如果你希望按排序后的格式保存数据，你需要用 > 或 tee 进行重定向。$ sort distro.list | tee distro.sorted 1337 Arch Debian [...] $ cat distro.sorted 1337 Arch Debian [...]按列排序复杂数据集有时候不止需要对每行的第一个字符进行排序。例如，假设有一个动物列表，每个都有其种和属，用可预见的分隔符分隔每一个“字段”（即数据表中的“单元格”）。这类由数据表导出的格式很常见，CSV（以逗号分隔的数据comma-separated values）后缀可以标识这些文件（虽然 CSV 文件不一定用逗号分隔，有分隔符的文件也不一定用 CSV 后缀）。以下数据作为示例：Aptenodytes;forsteri;Miller,JF;1778;Emperor Pygoscelis;papua;Wagler;1832;Gentoo Eudyptula;minor;Bonaparte;1867;Little Blue Spheniscus;demersus;Brisson;1760;African Megadyptes;antipodes;Milne-Edwards;1880;Yellow-eyed Eudyptes;chrysocome;Viellot;1816;Southern Rockhopper Torvaldis;linux;Ewing,L;1996;Tux对于这组示例数据，你可以用 --field-separator （在 BSD 和 Mac 用 -t，在 GNU 上也可以用简写 -t ）设置分隔符为分号（因为该示例数据中是用分号而不是逗号，理论上分隔符可以是任意字符），用 --key（在 BSD 和 Mac 上用 -k，在 GNU 上也可以用简写 -k）选项指定哪个字段被排序。例如，对每行第二个字段进行排序（计数以 1 开头而不是 0）：sort --field-separator=";" --key=2 Megadyptes;antipodes;Milne-Edwards;1880;Yellow-eyed Eudyptes;chrysocome;Viellot;1816;Sothern Rockhopper Spheniscus;demersus;Brisson;1760;African Aptenodytes;forsteri;Miller,JF;1778;Emperor Torvaldis;linux;Ewing,L;1996;Tux Eudyptula;minor;Bonaparte;1867;Little Blue Pygoscelis;papua;Wagler;1832;Gentoo结果有点不容易读，但是 Unix 以构造命令的管道方式而闻名，所以你可以使用 column 命令美化输出结果。使用 GNU column：$ sort --field-separator=";" \ \--key=2 penguins.list | column --table --separator ";" Megadyptes antipodes Milne-Edwards 1880 Yellow-eyed Eudyptes chrysocome Viellot 1816 Southern Rockhopper Spheniscus demersus Brisson 1760 African Aptenodytes forsteri Miller,JF 1778 Emperor Torvaldis linux Ewing,L 1996 Tux Eudyptula minor Bonaparte 1867 Little Blue Pygoscelis papua Wagler 1832 Gentoo对于初学者可能有点不好理解（但是写起来简单），BSD 和 Mac 上的命令选项：$ sort -t ";" \ -k2 penguins.list | column -t -s ";" Megadyptes antipodes Milne-Edwards 1880 Yellow-eyed Eudyptes chrysocome Viellot 1816 Southern Rockhopper Spheniscus demersus Brisson 1760 African Aptenodytes forsteri Miller,JF 1778 Emperor Torvaldis linux Ewing,L 1996 Tux Eudyptula minor Bonaparte 1867 Little Blue Pygoscelis papua Wagler 1832 Gentoo当然 -k 不一定非要设为 2。任意存在的字段都可以被设为排序的键。逆序排列你可以用 --reverse（BSD/Mac 上用 -r，GNU 上也可以用简写 -r）选项来颠倒已经排好序的列表。$ sort --reverse alphabet.list z y x w [...]你也可以把输出结果通过管道传给命令 tac 来实现相同的效果。按月排序（仅 GNU 支持）理想情况下，所有人都按照 ISO 8601 标准来写日期：年、月、日。这是一种合乎逻辑的指定精确日期的方法，也可以很容易地被计算机理解。也有很多情况下，人类用其他的方式标注日期，包括用很名字随意的月份。幸运的是，GNU sort 命令能识别这种写法，并可以按月份的名称正确排序。使用 --month-sort（-M）选项：$ cat month.list November October September April [...] $ sort --month-sort month.list January February March April May [...] November December月份的全称和简写都可以被识别。人类可读的数字排序（仅 GNU 支持）另一个人类和计算机的常见混淆点是数字的组合。例如，人类通常把 “1024 kilobytes” 写成 “1KB”，因为人类解析 “1 KB” 比 “1024” 要容易且更快（数字越大，这种差异越明显）。对于计算机来说，一个 9 KB 的字符串要比诸如 1 MB 的字符串大（尽管 9 KB 是 1 MB 很小一部分）。GNU sort 命令提供了--human-numeric-sort（-h）选项来帮助正确解析这些值。$ cat sizes.list 2M 12MB 1k 9k 900 7000 $ sort --human-numeric-sort 900 7000 1k 9k 2M 12MB有一些情况例外。例如，“16000 bytes” 比 “1 KB” 大，但是 sort 识别不了。$ cat sizes0.list 2M 12MB 16000 1k $ sort -h sizes0.list 16000 1k 2M 12MB逻辑上来说，这个示例中 16000 应该写成 16 KB，所以也不应该全部归咎于GNU sort。只要你确保数字的一致性，--human-numeric-sort 可以用一种计算机友好的方式解析成人类可读的数字。随机排序（仅 GNU 支持）有时候工具也提供了一些与设计初衷相悖的选项。某种程度上说，sort 命令提供对一个文件进行随机排序的能力没有任何意义。这个命令的工作流让这个特性变得很方便。你可以用其他的命令，像 shuf ，或者你可以用现在的命令添加一个选项。不管你认为它是一个臃肿的还是极具创造力的用户体验设计，GNU sort 命令提供了对文件进行随机排序的功能。最纯粹的随机排序格式选项是 --random-sort 或 -R（不要跟 -r 混淆，-r 是 --reverse 的简写）。$ sort --random-sort alphabet.list d m p a [...]每次对文件运行随机排序都会有不同的结果。结语GNU 和 BSD 的 sort 命令还有很多功能，所以花点时间去了解这些选项。你会惊异于 sort 的灵活性，尤其是当它和其他的 Unix 工具一起使用时。via: https://opensource.com/article/19/10/get-sorted-sort作者：Seth Kenlon 选题：lujun9972 译者：lxbwolf 校对：wxy本文由 LCTT 原创编译，Linux中国 荣誉推出