Lugick Wang's Blog
0%

排序算法——冒泡排序

发表于 Disqus：

前言

冒泡排序，以从小到大排序为例。

原理

每次都从头开始遍历未排序的数组，两两比较，如果前一位比后一位大，则交换位置，一直到未排序的最后一位。每次循环后将未排序数组中的最大值归位。如果一次循环中没有过任何交换，则退出循环。

算法实现

swift 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func bubbleSort(array: inout [Int]) -> [Int] {
    if array.count > 1 {
        
        for i in 0..<array.count - 1{
            var swapped = false

            for j in 0..<array.count - 1 - i{
                if array[j] > array[j+1] {
                    let temp = array[j]
                    array[j] = array[j+1]
                    array[j+1] = temp
                    swapped = true
                }
            }
            print("第\(i+1)次后")
            print(array)
            
            if swapped == false { break }
        }
    }
    return array
}

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var d = [3,44,38,5,47,15]
bubbleSort(array: &d)

第1次后
[3, 38, 5, 44, 15, 47]
第2次后
[3, 5, 38, 15, 44, 47]
第3次后
[3, 5, 15, 38, 44, 47]
第4次后
[3, 5, 15, 38, 44, 47]

//只进行了一次循环
var e = [1,2,3,4,5,6]
bubbleSort(array: &e)

第1次后
[1, 2, 3, 4, 5, 6]

动画展示

来自：visualgo