具有数组冒泡排序的交换数与具有插入排序的单个移位数相同

Question

我尝试在这里放置冒泡排序计数器 -

for (i = 0; i < n-1; i++)         
   for (j = 0; j < n-i-1; j++)  
       if (arr[j] > arr[j+1]) {
          swap(&arr[j], &arr[j+1]); 
          printf("%d of %d\n", i, n);
          count++; // here
       }

并在这里插入排序 -

for (i = 1; i < n; i++) { 
    key = arr[i]; 
    j = i-1; 
    while (j >= 0 && arr[j] > key) { 
        arr[j+1] = arr[j]; 
        j = j-1; 
        count++;
    } 
    arr[j+1] = key;
}

并尝试了各种大小的输入数组,范围分别为10,20,50,1000等,但在所有情况下,数组的带有冒泡排序的交换数与插入排序的单个移位数相同.有人可以解释一下吗？我的中心困惑在于交换的数量与移位的数量是一样的,因为它们是阵列中移动元素的完全不同的机制.

Answer 1

插入排序的每个班次都只能纠正一次倒置

气泡排序中的每次交换都只能纠正一次反转.

因此对于相同的源数据,反转计数是相似的,并且交换和移位的数量是相等的.

这两个算法逐步消除了反转.请注意,选择排序例如使用另一种策略:它消除了最小元素的所有反转,但可能为交换元素创建新的反转,然后消除第二个最小元素的所有反转,依此类推.

通常,插入排序工作得更快,因为移位更有效,减少元素移动.

插入排序的平均比较大约n^/4是随机值(n^2/2在最坏的情况下)(Sedgewick书),而冒泡排序执行~n^2/2比较(如果不使用早期停止)