查看完整版本: 基础Case:冒泡排序

基础Case:冒泡排序

很经典的题目,不多说背景了,开门见山

[size=4][b]一.原理[/b][/size]
摘自:[url=http://baike.baidu.com/view/254413.htm]http://baike.baidu.com/view/254413.htm[/url]
   依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。

[size=4][b]二.Ruby实现[/b][/size]
0. 先拿一个例子分析,比如4,3,2,1
   先比较4和3,交换,现在是3,4,2,1
   然后比较4和2,交换,现在是3,2,4,1
   再比较4和1,交换,现在是3,2,1,4
   现在最大的数字4已经到最后一位去了
   从头再来比较3和2
   依此类推......
   最后得到1,2,3,4

1. 先来定一个方法吧,传入一个数组作为参数[code]def bubblesort(arr)
end[/code]2.由上面的例子不难看出,对n个数进行排序,一共要排n-1次。且每一次排序内部，交换的次数是递减的。
也就是说，第一次排序，交换4次，得到3，2，1，4
         第二次排序，交换3次，得到2，1，3，4
         第三次排序，交换2次，得到1，2，3，4
所以我们用一个downto迭代来表示交换的次数，代码如下[code]def bubblesort(arr)
  (arr.length-1).downto(1) do |j|
  end
end[/code]3.这个downto迭代从arr.length-1到1，一共执行arr.length-1次，并且参数j的值表示交换的次数。现在开始写交换[code]def bubblesort(arr)
  (arr.length-1).downto(1) do |j|
    j.times do |i|
      if arr[i] > arr[i+1]
        arr[i],arr[i+1] = arr[i+1],arr[i]
      end
    end
  end
  arr #省略了return,return arr表示方法最后返回arr
end[/code]这里用到了ruby的并行赋值特性，在其他不支持并行赋值的语言里,交换两个变量的值需要三步和一个多余的临时变量。
如此我们的冒泡排序就做好了。来试一下:[code]bubblesort([5,4,3,2,1])
#=>[1,2,3,4,5][/code]4.还没完，假如我们对1,2,3,4,6,5进行排序，第一次排序结束后已经得到了正确的结果1,2,3,4,5,6
但是程序还会继续执行4次。执行4次没什么，但假如我们的数组是1,2...,997,999,998那么程序在得到正确结果后还会执行997次！
这就不好了，我们应该让他得到正确结果后就停止执行。
思路就是得到正确结果后再执行一次，不会产生任何变化。等价于只要一次排序后没有任何变化，那么得到的已经是正确结果了。
我们要做的就是在每次排序之后验证一下与排序之前有没有变化就行了。最终的代码如下[code]def bubble(arr)
  (arr.length-1).downto(1) do |j|
    a1 = arr.dup   #现在a1等于arr了
    j.times do |i|
      if arr[i] > arr[i+1]
        arr[i],arr[i+1] = arr[i+1],arr[i]
      end
    end
    break if a1 == arr #验证这次排序是否产生了变化，如果没有，就跳出循环，返回结果
  end
  arr
end[/code][size=4][b]三.声明[/b][/size]
这段代码只用于学习冒泡排序和练习ruby用。其效率远低于数组的sort方法。真正对[5,4,3,2,1]进行排序请使用[code][5,4,3,2,1].sort[/code]

多谢分享

学习学习

studying~~~

自己看了题目也写了一个...
请多多指教[code]arr=[2,1,5,3,4,7,5,6,9,20]
def sort(arr)
  for i in 0 ... (arr.length-1)
   if arr[i] > arr[i+1]
        arr[i],arr[i+1] = arr[i+1],arr[i]
    end
  end
  puts arr
end

sort(arr)[/code]