-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patht1-buble-sort.md
87 lines (55 loc) · 3.63 KB
/
t1-buble-sort.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# 冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字 的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的 顶端，所以这个算法才被称为“冒泡排序”。
## 步骤
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
## 举例
1.对数字 1~9 进行排序
2.在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，就交换这两个数字的位置。
3.由于 6 < 7，所以交换这两个数字。
4.完成后，天平往左移动一个位置，比较两个数 字的大小。此处 4 < 6，所以无须交换。
5.继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。
6.不断对数字进行交换，天平最终到达了最左边。通过这一系列操作，序列中最小的数字就会移动到最左边。
7.最左边的数字已经归位。
8.将天平移回最右边，然后重复之前的操作，直到天平到达左边第 2 个位置为止。
9.当天平到达左边第 2 个位置时，序列中第 2 小的数字也就到达了指定位置。
10.将天平再次移回最右边，重复同样的操作直到所有数字都归位为止。
11.由于 9 > 6，所以交换这两个数字。
12.由于 9 > 8，所以交换这两个数字。
13.排序完成
## 代码
```swift
func bubleSort(_ numbers: [Int]) -> [Int] {
var nums = numbers
let n = nums.count
for i in 0..<n {
for j in 0..<(n-1-i) {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j+1)
}
}
}
return nums
}
let nums = [3, 42, 1, 5, 34, 20, 9]
bubleSort(nums)
```
## 性能
在冒泡排序中，第 1 轮需要比较 n-1 次，第 2 轮需要比较 n-2 次......第 n-1 轮需要比较 1 次。因此，总的比较次数为 (n - 1) + (n - 2) + ... + 1 ≈ n^2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作;反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时 间复杂度为 O(n^2)。