需要帮助理解Ruby冒泡排序解决方案中的语法/逻辑

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

具体来说，我在理解until回路和sorted = true和sorted = false部分时遇到了一些麻烦。我在这里做了一些阅读，我想我得到，如果需要改变数组仍然，sorted被设置为false和循环继续。但如果有人能再给我解释一次，我会很感激的。

看起来times循环只对每个数组元素- 1执行一次，然后交换位置。until循环是如何发挥作用的?

Answer 1

.times循环对数组进行一次遍历，将每个元素与其相邻元素进行比较，如果顺序错误则交换它们。

外部的until sorted循环重复这个过程，直到没有任何变化。此时数组已排序完毕。

sorted变量记录了在最后一次遍历数组时是否交换了任何元素。如果我们这样做了，数组改变了，我们还没有完成。另一方面，如果没有交换元素，则不执行sorted = false, sorted保留true，并且可以退出外循环。

Answer 2

您是正确的，它遍历数组，检查值并在需要时进行交换-如果在该过程中进行了交换，则认为数组未排序并设置sorted = false。如果是这种情况，until循环将确保整个新的传递在数组中发生，以再次重做该过程。until循环停止的唯一情况是，在一次传递过程中没有执行任何交换操作。在每个until循环开始时，sorted被设置为true，因为它假设这将是最后一次传递-除非进行了将sorted设置为false的交换，否则它将至少再执行一次传递。

查看http://visualgo.net/sorting.html#如果你想要一个简洁的动画来可视化各种排序算法中发生的事情。