0

我正在阅读 Robertsedwick 的 C++ 排序算法

属性1：插入排序和冒泡排序使用线性数量的比较和交换文件，每个元素对应的反转次数最多为常数。

在另一种类型的部分排序文件中，我们可能已经将一些元素附加到排序文件中，或者编辑了排序文件中的一些元素以更改它们的 kesy。插入排序是此类文件的有效方法；冒泡排序和选择排序不是。

属性 2：插入排序使用线性数量的比较，并交换最多具有恒定数量的元素的文件，这些元素具有超过恒定数量的相应反转。

我对上述属性的问题是

  1. 我无法区分属性 1 和属性 2？任何人都可以在这里解释我吗？

  2. 上面提到的属性 2 作者提到插入排序是最好的而不是冒泡排序和选择排序的依据是什么？

如果举例说明就好了。

感谢您的时间和帮助

4

1 回答 1

3

<因此，存在排序顺序的反转，i < j但是a[i] > a[j].

  • 属性 1. 考虑序列2 1 4 3 6 5 8 7 10 9...。每个元素相对于其左侧或右侧的邻居都是无序的，但相对于所有其他元素是有序的。所以每个元素都有一个恒定数量的反转，在这种情况下是一个。该属性表示所有元素都可能有点乱序。

    冒泡排序和插入排序都将在线性时间内运行。冒泡排序将只需要一次通过来更正顺序，因为它交换相邻元素并通过另一次确认。插入排序只需对每个元素进行一次比较和交换。

  • 属性2.这个属性更强。除了能够让所有元素有点乱序之外，现在你还可以拥有一些非常乱序的元素。考虑与之前相同的序列，但最小元素和最大元素移动到相反的两端：n 2 4 3 6 5 8 7 10 9...1. 现在1和n所有其他元素都出现故障。

    插入排序仍将在线性时间内执行。和以前一样，大多数元素只需要很少的比较和交换，但是有一些可以进行顺序n比较和交换。在这个例子中，第一个n-1元素需要几个比较和交换（好的，所以2只有一个）才能到位，最后一个元素需要n-1比较和交换 -2*(n-1) + 1*(n-1)是 order n。

    Bubble sort has a much harder time in this example. Each pass through can only move the 1 a single step backwards. Thus it will take at least (n-1) passes in which (n-1) comparisons are done before completion -- this is multiplicative (n-1)*(n-1) is order n^2. (You could also run bubble sort in the opposite direction, in which case the largest element at the beginning would slowly move to the other end instead.)

于 2012-11-02T12:44:02.897 回答