UDN-企业互联网技术人气社区

板块导航

浏览  : 851
回复  : 0

[其它] 深入浅出 Swift 算法系列一:冒泡排序

[复制链接]
呵呵燕的头像 楼主
发表于 2016-9-13 21:20:16 | 显示全部楼层 |阅读模式
  什么是冒泡排序(Bubble Sort)

  首先,我们先瞄一眼冒泡排序算法的定义:

  冒泡排序 是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。—— 维基百科

  单纯看定义可能比较抽象,没关系,接下来我们将通过一个简单的例子来仔细了解冒泡排序的原理。

  举个栗子

  假如需要对 1 4 6 2 8 这五个数按照从大到小的排序进行排列,那么我们应该怎么入手解决呢?

l.jpg


  首先,比较第 1 位数和第 2 位数的大小。很明显 1 要小于 4,所以我们把 1 和 4 的位置互换一下。

k.jpg


  然后,我们继续比较第 2位数和第 3 位数,发现 1 要小于 6,因此把 1 和 6 的位置互换。

j.jpg


  继续比较第 3 位和第 4 位数,1 要小于 2,根据要求把 1 和 2 的位置互换。

i.jpg


  最后比较第 4 位和第 5 位数,显然 1 小于 8,同理把 1 和 8 的位置互换。

h.jpg


  经过这样一轮操作,我们已经不知不觉中把数字 1 的位置放好了,1 是这五个数字中数值最小的,应该排在最后一位。

  我们回过头来,看看刚刚才的排序过程,1 的位置经由交换慢慢“浮”到数列的顶端,是不是很像气泡上浮的过程,这也是冒泡排序算法这个名字的由来。

g.jpg


  第一轮操作结束后,我们把五个数字中数值最小的 1 摆放好了。第二轮操作我们将会把五个数字中数值第二小的 2 摆放好。仔细想想这个规律,是不是很有意思?同样按照第一轮的规则进行操作,先比较第 1 位和第 2 位数,依此类推,过程如下。

f.jpg


  好了,现在还剩下三个数字没摆好,按照这样的规则只要再进行两轮操作就能把剩下三个数字都摆好,没错是两轮,这很容易理解吧。

  总结

  经过上述分析,我们可以看到,冒泡排序的理念十分简单:不断比较相邻的两个元素,如果它们的顺序不符合要求就互相调换。

  Swift 3.0 实现

  最后我们来看一下具体的代码实现:

  1.   var numbersArray = [1, 4, 6, 2, 8]

  2.   for i in 0...(numbersArray.count - 2) { //n个数进行排序,只要进行(n - 1)轮操作

  3.   //开始一轮操作

  4.   for j in 0...(numbersArray.count - i - 2){

  5.   if numbersArray[j] < numbersArray[j + 1] {

  6.   //交换位置

  7.   var temp = numbersArray[j]

  8.   numbersArray[j] = numbersArray[j + 1]

  9.   numbersArray[j + 1] = temp;

  10.   }

  11.   }

  12.   }

  13.   print(numbersArray)
复制代码


  源代码地址

  Github 地址(持续更新中,欢迎 Star):https://github.com/Zentopia/Algorithm

  参考文献

  啊哈!算法

  维基百科

原文作者:薛定谔的番茄  来源:开发者头条
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部