冒泡排序解法讲解

Question

在网上看了什么是冒泡排序，感觉自己理解的很好，但是别人给我的解法不是很直观。

下面是创建使用冒泡排序方法对数组进行排序的方法的解决方案：

def bubble_sort(arr)
  sorted = false
  until sorted
    sorted = true
    (arr.count - 1).times do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
        sorted = false
      end
    end
  end

  arr
end

我有点难以理解 "sorted" 一词在这里的作用。我知道有一个 .sort 方法，但我找不到任何排序的方法，而且循环如何知道如何结束并不完全清楚。

谁能解释一下 "sorted" 一词的含义？

Answer 1

不是方法，是局部变量。特别是，这些类型的变量称为标志。它在相对较少的替代值之间切换以保持算法的内部状态。在本例中，它在false和true之间切换，用于控制是否跳出until循环。

Answer 2

sorted是一个布尔变量，用来表示排序是否完成。

最初，sorted 设置为 false（假设数组尚未排序）。主（外）循环的入口条件检查 sorted 是真还是假，并且如您所见，循环继续直到 sorted 为真。

每次通过外循环时，sorted 开始被设置为 true。但是随后内部循环检查数组中是否有任何值的顺序不正确，如果不是，则交换它们，并将 sorted 设置为 false。

只有当内部循环遍历整个数组而不需要交换任何值时，sorted 才会保持为真并且外部循环退出。

冒泡排序解法讲解

Bubble sort solution explanaition

ruby

sorting

bubble-sort