我正在阅读 Robertsedwick 的 C++ 排序算法
Property 1: Insertion sort and bubble sort use a linear number of comparisions and exchanges for files with at most a constant number of inversions corresponding to each element.
在另一种类型的部分排序的文件中，我们可能已经将一些元素附加到排序文件中，或者已经编辑了排序文件中的一些元素以更改它们的 kesy。插入排序是此类文件的有效方法；冒泡排序和选择排序不是。
Property 2: Insertion sort uses a linear number of comparisions and exchanges for files with atmost a constant number of elements having more than a constant number of corresponding inversions.
我对上述属性的问题是
我无法区分属性 1 和属性 2？有人可以在这里解释一下吗？
作者在上面提到的属性 2 中插入排序最好而不是冒泡排序和选择排序的依据是什么？
如果能举例说明就好了。
感谢您的时间和帮助
最佳答案
因此，排序顺序为 < 的反转有没有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)是订单n.在此示例中，冒泡排序要困难得多。每次穿越只能移动
1退一步。因此至少需要(n-1)通过其中(n-1)比较在完成之前完成——这是乘法(n-1)*(n-1)是订单n^2. (你也可以在相反的方向运行冒泡排序，在这种情况下，开始的最大元素会慢慢移动到另一端。)
关于algorithm - 插入、选择、冒泡排序分析与反演 Robert Sedgewick，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13195198/