使用排序方法对算法时间进行排序
Sorting algorithm times using sorting methods
所以我刚刚了解了排序算法的冒泡、合并、插入、排序等。它们的排序方法似乎都非常相似，在我看来它们的方法变化很小。那么为什么它们会产生如此不同的排序时间，例如 O(n^2) 与 O(nlogn)
你看到的"similarity"(?!)完全是虚幻的
基本的 O(N 平方) 方法，一遍又一遍地重复他们的工作，没有利用任何在 "previous step" 上完成的任何工作的 "next step"。因此，第一步花费的时间与 N 成正比，第二步花费的时间与 N-1 成正比，依此类推——从 1 到 N 的整数的总和与 N 的平方成正比。
例如，在选择排序中，您每次都在寻找 I:N 部分中的最小元素，其中 I 首先是 0，然后是 1，等等。这是（而且必须）完成的通过检查所有这些元素，因为之前没有注意通过利用先前的任何优势来为后续的传递提供更少的工作量。一旦找到最小的元素，就将它与第 I 个元素交换，递增 I，然后继续。当然是 O(N 平方)。
高级的 O(N log N) 方法结构巧妙，可以利用前面步骤中完成的后续步骤。与基本方法相比，这种差异是如此普遍和深刻，以至于如果一个人无法察觉它，那主要是关于一个人感知的敏锐度，而不是方法本身:-)。
例如，在归并排序中，您逻辑上将数组分成两部分，0 到半长和半长到长。一旦对每一半进行排序（以相同的方式递归，直到长度变得足够短），将合并两半，这本身就是一个线性子步骤。
因为你每次都减半，你显然需要与 log N 成比例的步数，而且，由于每一步都是 O(N)，显然你会得到非常理想的 O(N log N) 作为结果。
Python 的 "timsort" 是一个 "natural mergesort"，即合并排序的变体，调整为利用数组的已排序（或反向排序）部分，它可以快速识别并避免花费任何进一步的工作。这不会改变 big-O，因为那是关于 worst-case 的时间——但是 expected 时间会进一步下降，因为在很多实际情况中-生活案例有些部分分类 存在。
（请注意，根据 big-O 的严格定义，快速排序一点也不快——最坏的情况是与 N 的平方成正比，当你每次都碰巧选择一个糟糕的主元时... expected-time 明智的是，虽然不如 timsort 好，因为在现实生活中，你反复选择灾难枢轴的情况非常罕见......但是，最坏-情况，他们可能发生！-)。
timsort 如此 好得让即使是非常有经验的程序员也大吃一惊。我不算数，因为我是发明家 Tim Peters 的朋友，也是 Python 的狂热分子，所以我的偏见很明显。但是，考虑...
...我记得 "tech talk" 在 Google 处出现了 timsort。前排坐在我旁边的是 Josh Bloch，他也是一位 Googler 和 Java 非凡的专家。谈话进行到一半时，他再也忍不住了 - 他打开笔记本电脑开始黑客攻击，看看它是否可能像出色、敏锐的技术演示所显示的那样好。
因此，timsort 现在也是最近版本的 Java 虚拟机 (JVM) 中的排序算法，尽管仅适用于用户定义的对象（基元数组仍然排序）老办法，quickersort [*] 我相信——我不知道哪个 Java 特性决定了这个 "split" 设计选择，我的 Java-fu 相当弱:-).
[*] 这本质上是快速排序加上一些用于枢轴选择的 hack 来尝试避免毒药案例——这也是 Python 在 Tim Peters 做出众多不朽贡献之前使用的他几十年来所做的重要作品。
结果有时会让有 CS 背景的人感到惊讶（像 Tim，我有幸拥有远古的学术背景，不是 CS，而是 EE，这有很大帮助:-)。比如说，您必须维护一个不断增长的数组，该数组始终在任何时间点进行排序，因为必须将新的传入数据点添加到数组中。
经典方法会使用二分法 O(log N) 来为每个新传入数据点找到正确的插入点——但是，为了将新数据放在正确的位置，您需要移动在它之后一个位置，即 O(N)。
使用 timsort，您只需将新数据点附加到数组，然后对数组进行排序——在这种情况下，timsort 的复杂度为 O(N)（因为它在利用第一个数组的已排序性质方面非常棒N-1 项！-).
您可以将 timsort 视为将 "take advantage of work previously done" 推向一个新的极端——其中不仅以前由算法本身完成的工作，而且还受到现实生活数据处理的其他方面的影响（导致提前排序的段），都被利用得淋漓尽致
然后我们可以进入桶排序和基数排序，它们通过利用项目的内部结构来改变讨论平面——在传统排序中，它限制一个人能够比较两个项目。
或者 Bentley 在他的不朽著作 "Programming Pearls" 中提出的一个类似示例——需要对包含数百万个唯一正整数的数组进行排序，每个正整数的长度限制为 24 位。
他用一个 16M 位的辅助数组解决了这个问题——毕竟只有 2M 字节——最初都是零：一个通过输入数组来设置辅助数组中的相应位，然后一个通过辅助数组数组以在找到 1s 的地方再次形成所需的整数——然后砰的一声，O(N) [并且非常迅速:-)] 对这个特殊但重要的情况进行排序！-)
所以我刚刚了解了排序算法的冒泡、合并、插入、排序等。它们的排序方法似乎都非常相似，在我看来它们的方法变化很小。那么为什么它们会产生如此不同的排序时间，例如 O(n^2) 与 O(nlogn)
你看到的"similarity"(?!)完全是虚幻的
基本的 O(N 平方) 方法，一遍又一遍地重复他们的工作，没有利用任何在 "previous step" 上完成的任何工作的 "next step"。因此，第一步花费的时间与 N 成正比，第二步花费的时间与 N-1 成正比，依此类推——从 1 到 N 的整数的总和与 N 的平方成正比。
例如，在选择排序中，您每次都在寻找 I:N 部分中的最小元素，其中 I 首先是 0，然后是 1，等等。这是（而且必须）完成的通过检查所有这些元素，因为之前没有注意通过利用先前的任何优势来为后续的传递提供更少的工作量。一旦找到最小的元素，就将它与第 I 个元素交换，递增 I，然后继续。当然是 O(N 平方)。
高级的 O(N log N) 方法结构巧妙，可以利用前面步骤中完成的后续步骤。与基本方法相比，这种差异是如此普遍和深刻，以至于如果一个人无法察觉它，那主要是关于一个人感知的敏锐度，而不是方法本身:-)。
例如，在归并排序中，您逻辑上将数组分成两部分，0 到半长和半长到长。一旦对每一半进行排序（以相同的方式递归，直到长度变得足够短），将合并两半，这本身就是一个线性子步骤。
因为你每次都减半，你显然需要与 log N 成比例的步数，而且，由于每一步都是 O(N)，显然你会得到非常理想的 O(N log N) 作为结果。
Python 的 "timsort" 是一个 "natural mergesort"，即合并排序的变体，调整为利用数组的已排序（或反向排序）部分，它可以快速识别并避免花费任何进一步的工作。这不会改变 big-O，因为那是关于 worst-case 的时间——但是 expected 时间会进一步下降，因为在很多实际情况中-生活案例有些部分分类 存在。
（请注意，根据 big-O 的严格定义，快速排序一点也不快——最坏的情况是与 N 的平方成正比，当你每次都碰巧选择一个糟糕的主元时... expected-time 明智的是，虽然不如 timsort 好，因为在现实生活中，你反复选择灾难枢轴的情况非常罕见......但是，最坏-情况，他们可能发生！-)。
timsort 如此 好得让即使是非常有经验的程序员也大吃一惊。我不算数，因为我是发明家 Tim Peters 的朋友，也是 Python 的狂热分子，所以我的偏见很明显。但是，考虑...
...我记得 "tech talk" 在 Google 处出现了 timsort。前排坐在我旁边的是 Josh Bloch，他也是一位 Googler 和 Java 非凡的专家。谈话进行到一半时，他再也忍不住了 - 他打开笔记本电脑开始黑客攻击，看看它是否可能像出色、敏锐的技术演示所显示的那样好。
因此，timsort 现在也是最近版本的 Java 虚拟机 (JVM) 中的排序算法，尽管仅适用于用户定义的对象（基元数组仍然排序）老办法，quickersort [*] 我相信——我不知道哪个 Java 特性决定了这个 "split" 设计选择，我的 Java-fu 相当弱:-).
[*] 这本质上是快速排序加上一些用于枢轴选择的 hack 来尝试避免毒药案例——这也是 Python 在 Tim Peters 做出众多不朽贡献之前使用的他几十年来所做的重要作品。
结果有时会让有 CS 背景的人感到惊讶（像 Tim，我有幸拥有远古的学术背景，不是 CS，而是 EE，这有很大帮助:-)。比如说，您必须维护一个不断增长的数组，该数组始终在任何时间点进行排序，因为必须将新的传入数据点添加到数组中。
经典方法会使用二分法 O(log N) 来为每个新传入数据点找到正确的插入点——但是，为了将新数据放在正确的位置，您需要移动在它之后一个位置，即 O(N)。
使用 timsort，您只需将新数据点附加到数组，然后对数组进行排序——在这种情况下，timsort 的复杂度为 O(N)（因为它在利用第一个数组的已排序性质方面非常棒N-1 项！-).
您可以将 timsort 视为将 "take advantage of work previously done" 推向一个新的极端——其中不仅以前由算法本身完成的工作，而且还受到现实生活数据处理的其他方面的影响（导致提前排序的段），都被利用得淋漓尽致
然后我们可以进入桶排序和基数排序，它们通过利用项目的内部结构来改变讨论平面——在传统排序中，它限制一个人能够比较两个项目。
或者 Bentley 在他的不朽著作 "Programming Pearls" 中提出的一个类似示例——需要对包含数百万个唯一正整数的数组进行排序，每个正整数的长度限制为 24 位。
他用一个 16M 位的辅助数组解决了这个问题——毕竟只有 2M 字节——最初都是零：一个通过输入数组来设置辅助数组中的相应位，然后一个通过辅助数组数组以在找到 1s 的地方再次形成所需的整数——然后砰的一声，O(N) [并且非常迅速:-)] 对这个特殊但重要的情况进行排序！-)