我正在尝试将冒泡排序方法应用到Ruby的简单编程问题中，但我遇到了一些麻烦。我理解的方法是先比较第一个元素的值和第二个元素的值，然后根据需要进行交换，但我无法在实际问题中实现它。是否有人愿意提供一个简短的例子，说明这在Ruby中如何工作？
在Ruby中使用冒泡排序算法对数组进行排序
5
- ppreyer
1
你真的需要冒泡排序吗？这是为教学还是实际目的？对于实际目的，Ruby 有许多排序方法可以返回相同的结果。例如，对于数组的升序排序，您只需执行以下操作：>> array.sort { |a, b| a <=> b } - Mauricio Moraes
14个回答
14
使用 while 循环正确实现冒泡排序
def bubble_sort(list)
return list if list.size <= 1 # already sorted
swapped = true
while swapped do
swapped = false
0.upto(list.size-2) do |i|
if list[i] > list[i+1]
list[i], list[i+1] = list[i+1], list[i] # swap values
swapped = true
end
end
end
list
end
- cluv
3
请解释为什么您的解决方案更加“正确”（不是说它不正确，而是您应该始终解释原因）... - Taryn East
是的，但如果块交换设置为 true，为什么答案是不正确的呢？反转布尔值如何改变返回值的正确性？在这种情况下，我会说：“因为冒泡排序在仍有交换发生时保持排序 - 一旦它找不到更多的交换，它就停止排序”，所以答案是正确的。 - Taryn East
冒泡排序之所以被称为冒泡排序，是因为在每次遍历中，最高的未排序值会“冒泡”到其正确的位置。我们可以利用它而不是在 while 循环内部循环所有元素，只使用
upto 循环未排序索引。由于我无法将答案添加到此问题中，请检查 gist：https://gist.github.com/shanshaji/5da49d1177cdf1cdc981f3dacc005b56 - Shan7
arr = [4,2,5,1]
loop until arr.each_cons(2).with_index.none?{|(x,y),i| arr[i],arr[i+1] = y,x if x > y}
p arr #=> [1, 2, 4, 5]
- steenslag
2
def bubble_sort(list)
return list if list.size <= 1 # already sorted
loop do
swapped = false
0.upto(list.size-2) do |i|
if list[i] > list[i+1]
list[i], list[i+1] = list[i+1], list[i] # swap values
swapped = true
end
end
break unless swapped
end
list
end
尽管我肯定会推荐一些运行时间比冒泡排序更好的东西 :)
- Chris Dargis
1
谢谢VanDarg...我正在跟随Chris Pine的教程，但他从未提到过循环或break unless这些术语。是否有其他方法来实现这段代码，比如使用while循环？ - ppreyer
2
这是我对最佳答案的版本。它仅在每个循环中调用一次数组的大小，而不是多次调用。一旦元素移动到数组的末尾，就不再进行比较。同时while循环会提前结束一个循环。当你遍历整个数组并且只进行了一次交换时，你已经完成了，因此无需进行另一次0次交换。
def bubble_sort(list)
iterations = list.size - 2
return list unless iterations > 0 # already sorted
swaps = 2
while swaps > 1 do
swaps = 0
0.upto(iterations) do |i|
if list[i] > list[i + 1]
list[i], list[i + 1] = list[i + 1], list[i] # swap values
swaps += 1
end
end
iterations -= 1
end
list
end
运行这个测试所需时间缩短了25%。
that_array = this_array = [22,66,4,44,5,7,392,22,8,77,33,118,99,6,1,62,29,14,139,2]
49.times {|variable| that_array = that_array + this_array}
bubble_sort that_array
- calasyr
1
只是重新编写@VanDarg的代码，使用while循环 （注意：代码未经测试...自行承担风险）
def bubble_sort(list)
return list if list.size <= 1 # already sorted
swapped = true
while swapped
swapped = false # maybe this time, we won't find a swap
0.upto(list.size-2) do |i|
if list[i] > list[i+1]
list[i], list[i+1] = list[i+1], list[i] # swap values
swapped = true # found a swap... keep going
end
end
end
list
end
编辑：更新了交换值，因为冒泡排序在仍有交换发生时会继续排序 - 一旦它不再发现任何交换，它就停止排序。请注意，这并不遵循@Doug的代码，但符合@cLuv的修复。
- Taryn East
1
def bubble_sort array
array.each do
swap_count = 0
array.each_with_index do |a, index|
break if index == (array.length - 1)
if a > array[index+1]
array[index],array[index+1] = array[index +1], array[index]
swap_count += 1
end
end
break if swap_count == 0 # this means it's ordered
end
array
end
- Basil
2
请在您的回答中提供更多细节。 - charleyh
这里没有必要使用each_with_index，最终你只需要一个计数器。 - SirUncleCid
0
另一种稍微不同的命名方式。
def bubble_sort(list)
return list if list.size <= 1
not_sorted = true
while not_sorted
not_sorted = false
0.upto(list.size - 2) do |i|
if list[i] > list[i + 1]
list[i], list[i + 1] = list[i + 1], list[i]
not_sorted = true
end
end
end
list
end
- nikkypx
0
类 数组
a = [6，5，4，3，2，1]
n = a.length
对于 j 在 0 到 n - 1 范围内 对于 i 在 0 到 n - 2 - j 范围内 如果 a[i] > a[i+1] tmp = a[i] a[i] = a[i+1] a[i+1] = tmp end end 结束
输出 a.inspect 结束类
对于 j 在 0 到 n - 1 范围内 对于 i 在 0 到 n - 2 - j 范围内 如果 a[i] > a[i+1] tmp = a[i] a[i] = a[i+1] a[i+1] = tmp end end 结束
输出 a.inspect 结束类
- Auwal Muhammad
0
def bubbleSort(list)
sorted = false
until sorted
sorted = true
for i in 0..(list.length - 2)
if list[i] > list[i + 1]
sorted = false
list[i], list[i + 1] = list[i + 1], list[i]
end
end
end
return list
end
- Anuj
0
这是我的看法，使用异或运算符：
def bubble(arr)
n = arr.size - 1
k = 1
loop do
swapped = false
0.upto(n-k) do |i|
if arr[i] > arr[i+1]
xor = arr[i]^arr[i+1]
arr[i] = xor^arr[i]
arr[i+1] = xor^arr[i+1]
swapped = true
end
end
break unless swapped
k +=1
end
return arr
end
- Adrian Statescu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接