插入排序中的比较和交换之间的区别

下面给出了应用于阵列A（基于零的索引）的插入排序算法的伪代码。 DEF比较（A，B）：如果A> B返回1 否则返回-1插入排序中的比较和交换之间的区别

for i : 1 to length(A) 
    j = i - 1 
    while j > 0 
      if compare(A[j-1], A[j]) > 0 
       swap(A[j], A[j-1]) 
       j = j - 1 
      else break

鉴于整数数组A中，发现比较函数调用和若干交换功能由呼叫的数目之间的差异以上算法应用于A.

让我们以A = {1，2，4，3}为例。如果我们在A作为上述应用插入排序我们所说的比较和交换功能sequeunce按照以下顺序

compare (A[0], A[1]) 
compare (A[1], A[2]) 
compare (A[2], A[3]) 
swap  (A[2], A[3]) 
compare (A[1], A[2])

这里比较函数被调用4次，交换函数被调用1次。答案是4-1 = 3.

我需要找到最佳的差异，而无需运行实际插入排序算法，其中需要O（n^2）。

来源

2017-07-25 LTim

“找到最佳差异”？ –

每i从2到length(A)的compare调用的次数会比除了在当前元素为1到i所有元素中最小的情况swap调用次数多了一个（从这种情况下，我们的出口当j变为0时循环）。答案将是length(A)-1 - minimal number occurrences。

minElement = A[1] // one-based array 
result = length(A) - 1 
for i = 2 to length(A) 
    if A[i] < minElement 
     minElement = A[i] 
     result = result - 1

来源

2017-07-25 09:44:40 DAle

把一个计数器放在while循环中，另一个在if的条件下。这两个减法将给出答案。

来源

2017-07-25 09:11:09 Sandeep

这个问题的最后一行是关于 – DAle

更具体的引用是'我需要找到最佳的差异，而不需要运行实际的插入排序算法，它需要O（n^2）。“＃ –

@DAle我现在读了它，但我个人认为，如果我们在这之下降低复杂性，它不会保持插入排序。它可以被称为一些其他的排序技术，然后 – Sandeep

插入排序中的比较和交换之间的区别

回答

相关问题