-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patht2-selection-sort.md
78 lines (54 loc) · 3.31 KB
/
t2-selection-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
# 选择排序
选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换” 这一操作的算法。在序列中寻找最小值时使用的是线性查找。
## 工作原理
1. 找到数组中的最小数字。 从索引 0 开始，遍历数组中的所有数字，并追踪最小数字的位置。
2. 使用索引 0 处的数字交换最小数字。现在，已排序部分仅包含索引 0 处的数字。
3. 转到索引 1 处。
4. 找到数组其余部分中的最小数字。 从索引 1 开始查看。再次循环直到数组结束并追踪最小数字。
5. 使用索引 1 处的数字交换最小数字。现在，已排序部分包含两个数字，索引 0 和索引 1。
6. 转到索引 2 处。
7. 从索引 2 开始，找到数组其余部分中的最小数字，并将其与索引 2 处的数字交换。现在，数组从索引 0 到 2 已排序; 此范围包含数组中的三个最小数字。
8. 并继续，直到没有数字需要排序。
## 例子
1.对数字 1~9 进行排序
2.使用线性查找寻找最小值，于是找到了最小值 1。
3.将最小值 1 与序列左边的 6 进行交换，最小值 1 归位。
4.然后在余下的数据中继续寻找最小值。这次我们找到了最小值 2。
5.将数字 2 与左边第 2 个数字 6 进行交换，最小值 2 归位。
6.重复同样的操作直到所有数字都归位为止。
7.排序完成
## 代码
```swift
func selectionSort(_ array: [Int]) -> [Int] {
guard array.count > 0 else {return array}
var tmpArr = array
for x in 0..<tmpArr.count - 1 {
var min = x
for y in x+1 ..< tmpArr.count {
if (tmpArr[y] < tmpArr[min]) {
min = y
}
}
if x != min {
tmpArr.swapAt(x, min)
}
}
return tmpArr
}
let list = [5,8,3,4,6]
selectionSort(list)
```
## 性能
选择排序使用了线性查找来寻找最小值，因此在第 1 轮中需要比较 n - 1 个数字，第 2 轮需要比较 n - 2 个数字......到第 n - 1 轮的时候就只需比较 1 个数字了。因此，总的比 较次数与冒泡排序的相同，都是(n-1)+(n-2)+...+1 ≈ n^2/2 次。
每轮中交换数字的次数最多为 1 次。如果输入数据就是按从小到大的顺序排列的， 便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为 O(n^2)
选择排序很容易理解，但执行速度慢 O(n^2)。它比插入排序更糟，但优于冒泡排序。查找数组其余部分中的最低元素很慢，特别是因为内部循环将重复执行。
堆排序使用与选择排序相同的原则，但使用了一种快速方法在数组的其余部分中查找最小值。 堆排序性能是 O(nlogn)。