arrays - 在使用递归的冒泡排序算法中记录交换次数？

Question

def bubble_sort(a)
  something_changed = false
  swap = 0 
  a[0...-1].each_with_index do |num, i|
    if a[i] > a[i + 1]
      a[i], a[i + 1] = a[i + 1], a[i]
      something_changed = true
      swap += 1
    end
  end
  bubble_sort(a)  if something_changed
  p swap
end

arr = [50, 60, 70, 20, 30, 10]
bubble_sort(arr)
# 0
# 1
# 1
# 3
# 3
# 3

所以我已经做了很长一段时间并尝试了各种方法。我已经设法理解了数组是如何通过冒泡排序进行排序的，并且我知道对于这个特定的数组，需要对要排序的数组进行 11 次替换。每次该方法递归运行时，我都可以打印出所有交换次数，但是对于我来说，我无法将这些数字分组到一个数组中，因此我可以将它们添加并显示 11，任何见解都很棒。我已经在 python 中完成了解决方案，并且工作正常，我只是想知道是否有一种方法可以在该方法递归运行时将这些数字分组在一起。提前致谢。

Answer 1

您也可以不使用全局变量:

def bubble_sort(a, swap_sum = 0)
  something_changed = false
  a[0...-1].each_with_index do |num, i|
    if a[i] > a[i + 1]
      a[i], a[i + 1] = a[i + 1], a[i]
      something_changed = true
      swap_sum += 1
    end
  end
  something_changed ? bubble_sort(a, swap_sum) : swap_sum
end

arr = [50, 60, 70, 20, 30, 10]
bubble_sort(arr) #=> 11