插入、选择、气泡分选的反相罗伯特·塞奇威克分析

Question

我正在阅读罗伯茨威克关于排序的C++算法

属性1:插入、排序和气泡排序使用线性数量的比较和交换文件，最多有与每个元素相对应的固定数量的反转。

在另一种类型的部分排序文件中，我们可能在一个排序文件中附加了几个元素，或者在一个排序文件中编辑了几个元素来更改它们的kesy。插入排序是处理此类文件的有效方法，而冒泡排序和选择排序则不是。

属性2:插入排序使用一个线性的比较和文件交换数，最多有一个固定数目的元素，其对应的反转数超过一个常量。

我对上述属性的问题是：

1. 我不能区分财产1和财产2？有人能在这里解释我吗？
2. 以上对于属性2作者所提到的插入排序是最好的，而不是冒泡和选择排序？

如果用例子来解释，那就更好了。

谢谢你的时间和帮助

Answer 1

所以，排序顺序是<的反转是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。 在这个例子中，冒泡排序要困难得多。每次通过只能向后移动1一步。因此，至少需要通过(n-1)，在完成之前进行(n-1)比较--这是乘法的(n-1)*(n-1)是order n^2。(您也可以向相反的方向运行气泡排序，在这种情况下，开头的最大元素将缓慢地移动到另一端。)