排序算法与完全排序算法的比较

Question

我希望找到使用不同排序算法对数组中的n元素进行排序的总比较。我不想手动执行(以防数组中的元素数量相当多)。如果数组中有8个元素包含以下元素3、24、66、34、8、-5、42、80，那么是否有“公式”来计算下面列出的每种排序算法的比较？我怎样才能找到每一个的比较？

1) Merge Sort

For example, if I use Merge sort manually in order to find the total numbers of
comparisons for 8 elements, this is what I get:

       3, 24, 66, 34, 8, -5, 42, 80    

     3, 24, 66, 34      8, -5, 42, 80    

    3, 24    66, 34     8, -5    42, 80   

 3  24    66    34       8   -5   42    80    

    3, 24    34, 66     -5, 8    42, 80 

      3, 24, 34, 66      -5, 8, 42, 80  

       -5, 3, 8, 24, 34, 42, 66, 80

 Total number of comparisons  needed to sort this array = 15 
 I would like to be able to do this using a formula, if possible, not manually.


2) Insertion sort

Answer 1

这不是一个容易的任务，因为它可以依赖于算法实现的细节，也不是n的纯函数。

实际上，您得到的是比较数的值的分布，这取决于输入的排列。通常，可以区分最佳情况(比较次数最少)、最坏情况(最大数)和平均情况(假设输入排列的各自概率时的数学期望)。

这些数字可以通过对程序的推理得到，但这通常是一项困难的任务(对于一般情况来说甚至是令人望而生畏的)，通常用近似来解决。

无论如何，您可以通过测试程序来获得它:声明一个计数器变量，并在进行比较的同时增加它。

我建议你做下面的练习：

• 就像我说的那样，
• 取n第一整数的序列；
• 生成输入的所有可能排列(就会有n!可能性--只要n保持较小，比如n最多10，这仍然是可管理的，10!=3628800)，并在每种情况下运行算法；
• (或者，您可以用随机数填充数组并重复多次)；
• 累积比较次数的直方图(对于每一个可能的比较数，计算实现排列的次数)，
• 观察和比较不同算法的直方图。

尽管n将保持适度，但您将观察最好的和最坏的情况，并更加小心地观察中心趋势和传播。这应该是有教育意义的。

使用相同的方法，您还可以观察到元素置换的数量。

Answer 2

这是不可能的，因为确切的数字取决于输入。这就是为什么你有乐观的复杂性，悲观，和平均有时也称为预期。突出的例子是快速排序的基本实现，它具有悲观复杂度O(n^2)。另一方面，气泡排序的乐观情况是O(n)。更多的例子：算法。

您唯一能做的就是计算每个问题实例，例如，使用比较函数。不过，我不确定每个实例的值是否很有意义。

Answer 3

通常人们不会做这样的计算。他们感兴趣的是评估算法的复杂性，即“比较的数目如何随着输入的大小而增加”。

例如，合并排序与O(n log )一起增长(平均)。这意味着合并排序的比较数并不比n log差，其中n是输入的大小。得到这个表达式的方法有几种，即主定理或树法。

实际上，我们可以证明，仅仅基于比较的算法不能比n个log进行更少的比较，这就是所谓的比较模型！比较算法

但是，排序可以在线性时间内完成，这取决于集合的类型，例如使用计数排序--一种直方图。