performance - 交换和转移有什么区别？

Question

这是插入排序的算法。第一个使用移位机制将值放在左排序部分。第二个交换连续的值，直到左边部分被排序。

1. 通过移动

   function insertionSort(array A)
   for i from 1 to length[A]-1 do
     value := A[i] 
       j := i-1
       while j >= 0 and A[j] > value do
           A[j+1] := A[j]
           j := j-1
       done
       A[j+1] = value
   done
   

2. 通过交换

   function insertionSort(array A)
   for (i =0; i<N; i++)
       for(int j=i; j>0; j--)
           if(less(A[j], A[j-1]))
               exch(A, j, j-1)
           else
               break;
       done
   done
   

维基百科关于插入排序的运行时分析是这样说的:

Worst case performance:   O(n^2) comparisons, swaps
Best case performance:    O(n) comparisons, O(1) swaps
Average case performance: O(n^2) comparisons, swaps

这符合算法2。但在算法1的情况下，分析变为:

Worst case performance:   O(n^2) comparisons, O(n) swaps
Best case performance:    O(n) comparisons, O(1) (no) swaps
Average case performance: O(n^2) comparisons, O(n) swaps

请说明移位和交换的含义。

Answer 1

回答一般问题:移动是将所有元素移动一个位置。交换是交换两个不同索引处的元素。

考虑以下数组:

a b c d e f

假设我们想将元素 e 放在第二个位置。

Shifting 随着shifting，数组变成了

a e b c d f

(序列 b c d 向右移动一位，为要插入的 e 腾出空间。)

交换交换后，数组变为

a e c d b f

(元素 b 和 e 交换了位置。)

对于您发布的特定算法，第一个算法只是将元素向右移动，直到找到新元素所在的位置，然后将其插入。第二种是将元素放在末尾，然后反复将新元素与前一个元素交换，直到发现它位于正确的位置。

编辑:关于两种算法的性能分析差异:我认为基于移位的算法的分析是有缺陷的，因为它没有计算移位 O(n) 个元素的工作(最差和平均情况下的性能) 在外循环的每次迭代期间。假设移位既不是比较也不是交换，它仍然代表工作(大约是交换的三分之一，但常数乘数在 big-O 计算中无关紧要。)

如果有人(错误地)忽略了转移的成本，那么这些差异就很容易解释了。在移位的情况下，外循环的每次迭代都需要内循环的 O(n) 次迭代，但只需要一次交换(一旦找到插入位置)。另一方面，基于交换的算法对除外循环的每次迭代执行的最后比较之外的所有内容进行交换。

附言我在 Wikipedia page on insertion sort 中没有看到两个单独的性能分析，我也看不到基于交换的实现。