我正在尝试将冒泡排序方法实现为一个简单的 Ruby 编码问题，但我遇到了一些麻烦。我理解这个想法是查看第一个元素的值并将其与第二个元素的值进行比较，然后相应地交换它们，但我似乎无法在实际问题中做到这一点。有人愿意提供一个简短的例子来说明这在 Ruby 中是如何工作的吗？
问问题
19645 次
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
于 2013-01-18T07:55:23.257 回答
7
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]
于 2013-01-30T20:33:33.093 回答
2
这是我的最佳答案版本。它只在数组上调用 size 一次，而不是每个循环。一旦元素移动到数组的末尾，它就不会比较元素。
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
于 2013-02-23T01:37:28.847 回答
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
虽然我肯定会推荐比bubblesort运行时间更好的东西:)
于 2012-06-18T21:38:39.667 回答
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
于 2013-05-25T18:29:51.083 回答
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 的修复
于 2012-06-18T23:42:58.313 回答
0
老套
def bubble_sort(random_numbers)
for i in 0..random_numbers.size
for j in i+1..random_numbers.size-1
random_numbers[i], random_numbers[j] = random_numbers[j], random_numbers[i] if(random_numbers[i] > random_numbers[j])
end
end
random_numbers
end
于 2014-06-25T13:05:07.460 回答
0
这是我的代码。我喜欢使用 (arr.length-1)。对于循环，您还可以使用诸如 until、while、for、upto、loop do 等迭代。有趣的是尝试不同的东西来看看它是如何工作的。
def bubble_sort(arr) #10/17/13 took me 8mins to write it
return arr if arr.length <= 1
sorted = true
while sorted
sorted = false
(arr.length-1).times do |i|
if arr[i] > arr[i+1]
arr[i], arr[i+1] = arr[i+1], arr[i]
sorted = true
end
end
end
arr
end
于 2013-10-18T06:19:57.303 回答
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
于 2013-04-16T05:15:49.800 回答
0
如果您不想使用这条有趣的交换线（IMO）：
arr[i], arr[j] = arr[j], arr[i]
这是我的看法：
def bubble_sort(arr)
temp = 0
arr.each do |i|
i = 0
j = 1
while (j < arr.length)
if arr[i] > arr[j]
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
p arr
end
i+=1
j+=1
end
end
arr
end
于 2014-01-24T08:12:26.367 回答
0
类数组
a = [6, 5, 4, 3, 2, 1]
n = a.长度
对于 0..n-1 中的 j
对于 i 在 0..n - 2 - j
如果 a[i]>a[i+1]
tmp = a[i]
a[i] = a[i+1]
a[i+1] = tmp
结尾
结尾
结尾
puts a.inspect
结尾
于 2015-01-26T11:18:21.417 回答
0
这是我使用运算符 XOR 的结果：
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
于 2014-09-11T10:29:28.167 回答
0
直截了当：
def bubble_sort(n)
return n if n.length <= 1
0.upto(n.length - 1) do |t|
0.upto(n.length - 2 - t) do |i|
if n[i] > n[i + 1]
n[i], n[i + 1] = n[i + 1], n[i]
end
end
end
n
end
于 2013-05-26T07:51:03.090 回答
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
于 2016-08-13T00:29:57.003 回答