冒泡排序 - Lab.Lawliet

731 字

4 分钟

冒泡排序

2022-02-09

2026-10-12

一、常规冒泡#

1
func bubbleSortA(nums: [Int]) -> [Int] {
2
    var nums = nums
3
    let count = nums.count
4

5
    for i in 0..<count {
6
        print("<")
7
        for j in (i + 1)..<count {
8
            if nums[i] > nums[j] {
9
                nums.swapAt(i, j)
10
            }
11
            print(nums)
12
        }
13
        print(">\n")
14
    }
15

16
    return nums
17
}

二、外层优化#

当发现在某一趟排序中没有发生交换，则说明排序已经完成，所以可以在此趟排序后结束排序，在每趟排序前设置flag，当其未发生变化时，终止算法

1
func bubbleSortB(nums: [Int]) -> [Int] {
2
    print("bubbleSortB")
3

4
    var nums = nums
5
    let count = nums.count
6

7
    for i in 0..<count {
8
        var swapFlag = true
9
        print("<")
10
        for j in (i + 1)..<count {
11
            if nums[i] > nums[j] {
12
                nums.swapAt(i, j)
13
                swapFlag = false
14
            }
15
            print(nums)
16
        }
17
        print(">\n")
18
        if swapFlag {
19
            break
20
        }
21
    }
22

23
    return nums
24
}

三、内层优化#

在每趟排序中，右面的许多元素已经是有序的结果了，可算法还是进行后面数值的排序，因此进行第二次优化

1
func bubbleSortC(nums: [Int]) -> [Int] {
2
    print("bubbleSortC")
3

4
    var nums = nums
5
    var boundary = nums.count - 1
6
    var lastSwapIdx = 0
7

8
    for _ in 0..<nums.count {
9
        var swapFlag = true
10
        print("<")
11
        for j in 0..<boundary {
12
            if nums[j] > nums[j+1] {
13
                nums.swapAt(j, j+1)
14
                swapFlag = false
15
                lastSwapIdx = j
16
            }
17
            print(nums)
18
        }
19
        print(">\n")
20
        boundary = lastSwapIdx
21
        if swapFlag {
22
            break
23
        }
24
    }
25

26
    return nums
27
}

四、对比#

1
let numbers: [Int] = [3, 5, 1, 11, 2, 4, 12]
2

3
bubbleSortA(nums: numbers)
4
bubbleSortB(nums: numbers)
5
bubbleSortC(nums: numbers)

输出：

1
<
2
[3, 5, 1, 11, 2, 4, 12]
3
[1, 5, 3, 11, 2, 4, 12]
4
[1, 5, 3, 11, 2, 4, 12]
5
[1, 5, 3, 11, 2, 4, 12]
6
[1, 5, 3, 11, 2, 4, 12]
7
[1, 5, 3, 11, 2, 4, 12]
8
>
9

10
<
11
[1, 3, 5, 11, 2, 4, 12]
12
[1, 3, 5, 11, 2, 4, 12]
13
[1, 2, 5, 11, 3, 4, 12]
14
[1, 2, 5, 11, 3, 4, 12]
15
[1, 2, 5, 11, 3, 4, 12]
16
>
17

18
<
19
[1, 2, 5, 11, 3, 4, 12]
20
[1, 2, 3, 11, 5, 4, 12]
21
[1, 2, 3, 11, 5, 4, 12]
22
[1, 2, 3, 11, 5, 4, 12]
23
>
24

25
<
26
[1, 2, 3, 5, 11, 4, 12]
27
[1, 2, 3, 4, 11, 5, 12]
28
[1, 2, 3, 4, 11, 5, 12]
29
>
30

31
<
32
[1, 2, 3, 4, 5, 11, 12]
33
[1, 2, 3, 4, 5, 11, 12]
34
>
35

36
<
37
[1, 2, 3, 4, 5, 11, 12]
38
>
39

40
<
41
>
42

43
bubbleSortB
44
<
45
[3, 5, 1, 11, 2, 4, 12]
46
[1, 5, 3, 11, 2, 4, 12]
47
[1, 5, 3, 11, 2, 4, 12]
48
[1, 5, 3, 11, 2, 4, 12]
49
[1, 5, 3, 11, 2, 4, 12]
50
[1, 5, 3, 11, 2, 4, 12]
51
>
52

53
<
54
[1, 3, 5, 11, 2, 4, 12]
55
[1, 3, 5, 11, 2, 4, 12]
56
[1, 2, 5, 11, 3, 4, 12]
57
[1, 2, 5, 11, 3, 4, 12]
58
[1, 2, 5, 11, 3, 4, 12]
59
>
60

61
<
62
[1, 2, 5, 11, 3, 4, 12]
63
[1, 2, 3, 11, 5, 4, 12]
64
[1, 2, 3, 11, 5, 4, 12]
65
[1, 2, 3, 11, 5, 4, 12]
66
>
67

68
<
69
[1, 2, 3, 5, 11, 4, 12]
70
[1, 2, 3, 4, 11, 5, 12]
71
[1, 2, 3, 4, 11, 5, 12]
72
>
73

74
<
75
[1, 2, 3, 4, 5, 11, 12]
76
[1, 2, 3, 4, 5, 11, 12]
77
>
78

79
<
80
[1, 2, 3, 4, 5, 11, 12]
81
>
82

83
bubbleSortC
84
<
85
[3, 5, 1, 11, 2, 4, 12]
86
[3, 1, 5, 11, 2, 4, 12]
87
[3, 1, 5, 11, 2, 4, 12]
88
[3, 1, 5, 2, 11, 4, 12]
89
[3, 1, 5, 2, 4, 11, 12]
90
[3, 1, 5, 2, 4, 11, 12]
91
>
92

93
<
94
[1, 3, 5, 2, 4, 11, 12]
95
[1, 3, 5, 2, 4, 11, 12]
96
[1, 3, 2, 5, 4, 11, 12]
97
[1, 3, 2, 4, 5, 11, 12]
98
>
99

100
<
101
[1, 3, 2, 4, 5, 11, 12]
102
[1, 2, 3, 4, 5, 11, 12]
103
[1, 2, 3, 4, 5, 11, 12]
104
>
105

106
<
107
[1, 2, 3, 4, 5, 11, 12]
108
>