排序算法中不同列表的比较次数

Number of comparisons for different lists in sorting algorithms

一直在研究排序算法，对每个排序算法的比较次数有疑问

假设我们有一个排序算法（插入排序、快速排序等等）。然后我想计算使用不同文件的比较次数。这些文件包含随机且无序的项目。例如，文件 1 有 10 个项目，包含字母 a 到 j。然后我们有另一个文件（同样是 10 项）包含整数 1 到 10。然后我们有另一个文件（10 项），包含浮点数 1.1111111111 到 10.1111111111。如果我们想使用任何排序算法对它们进行排序（对于第一个，我们按字母顺序排序，其他的从最小到最大排序）。

如果我们计算每个文件中的比较次数（例如，在快速排序算法中），它们是否相同，因为我们正在比较相同数量的项目，或者项目的长度是否会改变数量比较（a vs 10.1111111）？如果它们相同，那么是所有排序算法（至少我提到的那些）还是某些排序算法都是这样？我不认为这是一个很难的问题（抱歉），但我像往常一样想得太多了。我猜他们会是一样的，但我不是真的。有人愿意解释吗？

您正在考虑输入文件不同的算法性能。为了标准化这类问题，科学家已经为每个算法给出了 三种类型 的性能：

  1. 最佳情况 - 成本下限
  2. 最坏情况 - 成本上限
  3. 平均情况 - "Expected cost"

现在，如果您想获得它与特定输入进行比较的次数，那么您可以构建自己的数学模型。但是为了标准化，您可以考虑这三种类型。另一件事是，比较次数不随输入类型而变化，但数据的顺序不同。这意味着如果你将排序的输入传递给插入排序，它会给你 O (N) 与大约 N 次比较。但如果它是相反的形式，那么它就是最坏的情况。

排序分析如下：

参考：Princeton course

比较次数取决于初始状态。排序算法和具体实现

例如：

  • 该实现可以首先通过检查集合是否已经向上或向下排序以避免不必要的工作甚至最坏的情况。这有一个小的成本，但可以避免病理情况。对于同一组，在执行和不执行的实现之间的比较次数将非常不同。

  • 一些实现选择，例如 select 中的哪个元素作为 qsort() 中的枢轴，将极大地影响相同集合的比较次数。

  • 更糟糕的是：为了避免 qsort() 中的二次最坏情况（如 Kernighan 的论文 anti qsort 中所述，这种情况更容易被触发），可以实现 qsort() 使用一些随机源对枢轴值进行非确定性选择。对于这样的实现，比较的次数可能会有所不同，即使对于重复排序相同的集合也是如此。请注意，由于 qsort() 不稳定，如果某些元素比较相等，这可能会产生不同的顺序。

除非你知道初始状态和排序算法的具体实现，否则无法准确回答你老师的问题。即使是最好情况和最坏情况的数字也取决于实施细节。