算法学习 - 冒泡排序

原理

  1. 比较相邻的元素,如果第一个比第二个大,就交换他们两个。
  2. 对每一组相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以后的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到满意任何一对数字需要比较,则序列最终有序。

Swift实现

1
2
3
4
5
6
7
8
9
10
11
12
func bubble_sort(_ array: inout [Int]) {
for i in 0..<array.count - 1 {
for j in 0..<array.count - i - 1 {
if array[j] > array[j + 1] {
array.swapAt(j, j + 1)
}
}
}
}

var arrays: [Int] = [3, 6, 4, 2, 9, 8, 5]
bubble_sort(&arrays)

代码优化:

在某些情况下,循环还未终止,整个数组已经排好序,此时应及时终止循环。(冒泡每次都会比较相邻两个数并交换次数不对的组,若一次循环后,都没进行交换,则判断为已完成排序)

优化代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func bubble_sort(_ array: inout [Int]) {
var isChanged = false
for i in 0..<array.count - 1 {
isChanged = false
for j in 0..<array.count - i - 1 {
if array[j] > array[j + 1] {
array.swapAt(j, j + 1)
isChanged = true
}
}
if (!isChanged) {
break
}
}
}

时间复杂度

  • 冒泡排序的时间复杂度为O(n^2)

本文标题:算法学习 - 冒泡排序

文章作者:kim逸云

发布时间:2019年10月15日 - 10:10

最后更新:2020年01月03日 - 16:01

原始链接:http://cloverkim.com/bubble_sort.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。


------本文结束感谢阅读------
0%