sorting - 选择排序、插入排序、快速排序的场景

Question

如果有人可以对我的逻辑提出一些意见，我将非常感激。

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

我认为这与数组已经排序时类似，因此插入排序将是线性的，而选择排序将是二次的。

Which method runs faster for an array in reverse order, selection sort or insertion sort?

我认为它们的运行方式类似，因为每个位置的值都必须改变。插入排序最坏的情况是逆序，因此这意味着它是二次排序，然后选择排序也已经是二次排序。

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

由于它是随机排序的，我认为这意味着插入排序必须执行的操作次数是值数量的很多倍。如果是这样，那么它不是线性的。因此，它可能是二次的，或者可能略低于二次。

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

最大数字传递的次数不能超过可用空间，因为它应该始终接近其正确位置。所以，从第一个值(value)点到最后一个值(value)点，会被交换N次。

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

绘制快速排序时，可以在每个阶段的比较对象周围画一个三角形，即N高，N宽，这个三角形的面积等于执行比较的次数，即(N^2 )/2

Answer 1

以下是我对您的评论的评论:

Which method runs faster for an array with all keys identical, selection sort or insertion sort?

我认为这与数组已经排序时类似，因此插入排序将是线性的，而选择排序将是二次的。

是的，没错。插入排序将为每个元素执行 O(1) 工作，并访问 O(n) 个元素，总运行时间为 O(n)。无论输入结构如何，选择排序总是在时间 θ(n²) 内运行，因此它的运行时间将是二次的。

Which method runs faster for an array in reverse order, selection sort or insertion sort?

我认为它们的运行方式类似，因为每个位置的值都必须改变。插入排序最坏的情况是逆序，因此这意味着它是二次排序，然后选择排序也已经是二次排序。

你说得对，两种算法都有二次运行时间。这些算法实际上应该具有相对可比较的性能，因为它们将进行相同的比较总数。

Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?

由于它是随机排序的，我认为这意味着插入排序必须执行的操作次数是值数量的很多倍。如果是这样，那么它不是线性的。因此，它可能是二次的，或者可能略低于二次。

这应该花费二次时间(时间 θ(n²))。只取数组后三分之一的元素。这些元素中大约有三分之一是 1，为了将它们插入到已排序的序列中，需要将它们移动到数组下方 2/3 的位置以上。因此，所做的功至少为 (n/3)(2n/3) = 2n²/9，这是二次方。

What is the maximum number of times during the execution of Quick.sort() that the largest item can be exchanged, for an array of length N?

最大数字传递的次数不能超过可用空间，因为它应该始终接近其正确位置。所以，从第一个值(value)点到最后一个值(value)点，会被交换N次。

这里有一个相差一的错误。当数组大小为 1 时，最大元素无法再移动，因此最大移动次数为 N - 1。

About how many compares will quick.sort() make when sorting an array of N items that are all equal?

绘制快速排序时，可以在每个阶段的比较对象周围画一个三角形，即N高，N宽，这个三角形的面积等于执行比较的次数，即(N^2 )/2

这实际上取决于 Quick.sort() 的实现。使用三元分区的快速排序总共只能完成 O(n) 的工作，因为所有等于主元的值都被排除在递归调用中。如果没有这样做，那么您的分析就是正确的。

希望这有帮助!