为什么这个冒泡排序有效?

我在这里找到了这个冒泡排序算法的代码,想知道它的原理。

function bubbleSort(A)
  local itemCount=#A
  local hasChanged

  repeat
    hasChanged = false
    itemCount=itemCount - 1

    for i = 1, itemCount do
      if A[i] > A[i + 1] then
        A[i], A[i + 1] = A[i + 1], A[i]
        hasChanged = true
      end
    end
  until hasChanged == false
end

我假设以下代码:

A[i], A[i + 1] = A[i + 1], A[i]

与以下代码相同:

A[i] = A[i + 1]
A[i + 1] = A[i]

这会导致

A[i] = A[i + 1]

例如

A = { [1] = 3, [2] = 1 }

将会变成

A = { [1] = 1 , [2] = 1 }

为什么它没有这样做?

点赞
用户4433386
用户4433386

显然,正如你自己指出的那样,你的假设是错误的:

Lua 允许实际交换变量而不需要中间的临时赋值,就像你找到的冒泡排序算法一样。

因此,

    A[i],A[i + 1] = A[i + 1],A[i]

是可以正常工作的。

编辑:很难给出你还没有在这里已经给出的答案...

2015-02-16 11:23:04
用户3854787
用户3854787

正如您所知道的那样,您的假设是错误的。在Lua语言中,一个表达式可以返回多个值。因此,在一个表达式中,您也可以将结果赋值给多个变量。在您的片段中:

A[i], A[i + 1] = A[i + 1], A[i]

A[i+1], A[i] 的结果是在 任何值实际改变之前 进行评估的,这意味着当赋值发生时,A[i+1], A[i] 中的值被分配给了 A[i], A[i+1],就像预期的那样。

简而言之:首先,右侧的表达式被求值,然后才进行赋值本身。

2015-02-16 12:46:07