冒泡排序算法中的 Ruby 无限循环

Question

我已经使用 Ruby 构建了基本的冒泡排序算法，没有出现任何问题。代码如下:

def bubble_sort(arr)
 swapped=true
 while swapped
    swapped=false
    for j in 0..arr.length-2 do
      if arr[j]>arr[j+1]
        arr[j], arr[j+1] = arr[j+1], arr[j]
        swapped=true
      end
    end
 end
arr
end

现在，我正在尝试实现相同的方法，但具有接受代码块的功能。代码块部分工作正常，但是当没有提供代码块时，该方法应该像上面那样工作，虽然它在我看来在逻辑上是相同的，但由于某种原因，它进入了无限循环:

在“除非”这一行，它会检查条件并在必要时交换位置，并会跳过 yield 部分。我用rdebugger一步步调试，没找到原因。

def bubble_sort_by(arr)
  swapped = true
  while swapped
    swapped=false
    for i in 0..arr.length-2 do
      unless block_given?
        arr[i], arr[i+1] = arr[i+1], arr[i] if arr[i] < arr[i+1]
        swapped=true
      end #unless
    if block_given?
      if yield(arr[i], arr[i+1])>0
        arr[i], arr[i+1] = arr[i+1], arr[i]
        swapped=true
      end #if yield
    end #if block_given?
    end #for
  end #while
puts arr
return arr
end

Answer 1

快速回答:

arr[i], arr[i+1] = arr[i+1], arr[i] if arr[i] < arr[i+1]
swapped=true

应替换为:

if arr[i] < arr[i+1]
  arr[i], arr[i+1] = arr[i+1], arr[i]
  swapped=true
end

发生的事情是您总是将swapped设置为true，即使元素没有被交换。所以你陷入了无限循环。

现在进行一些代码清理...首先，而不是编写:

if(foo)
  # ...
end
unless(foo)
  # ...
end

让我们把它变成一个 if/else 语句:

def bubble_sort_by(arr) 
  swapped = true 

  while swapped 
    swapped=false 
    for i in 0..arr.length-2 do 
      if block_given? 
        if yield(arr[i], arr[i+1])>0 
          arr[i], arr[i+1] = arr[i+1], arr[i] 
          swapped=true 
        end 
      else 
        if arr[i] < arr[i+1] 
          arr[i], arr[i+1] = arr[i+1], arr[i] 
          swapped=true 
        end 
      end 
    end #for 
  end #while 

  return arr 
end

您可以按照@Aetherus 的建议进一步重构它以删除 while 循环，但我认为您会很高兴看到实际错误已修复。