蚊章汇 - 排序
type: channel
link: https://linuxcn.bwsl.wang/tag/%E6%8E%92%E5%BA%8F/
items: 为什么排序的复杂度为 O(N log N)
items: 在命令行用 sort 进行排序

为什么排序的复杂度为 O(N log N)
type: item
date: 2020-09-08T22:49:21+08:00
description: 基本上所有正而八经的算法教材都会解释像 快速排序 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) 对应的指令下限。任何物理上可实现的计算机都只能在给定时间内执行有限数量的指令，所以算法的…

在命令行用 sort 进行排序
type: item
date: 2019-12-09T14:54:54+08:00
description: 在 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 Y…