-
Notifications
You must be signed in to change notification settings - Fork 0
/
t3-insertion-sort.md
89 lines (57 loc) · 4.03 KB
/
t3-insertion-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
88
89
# 插入排序
插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据 陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
## 工作原理
- 把一系列数字放在一个未排序的堆里。
- 从堆中挑选一个数字。 你选择哪一个并不重要，但从堆顶挑选是最容易。
- 把这个数插入一个新的数组。
- 从未排序堆中再选择一个数字，并将其插入之前的数组中。 这个数字在第一个数字之前或之后，所以现在这两个数字被排序。
- 再从堆中选择一个数字，并将其插入到数组中的正确排序位置
- 继续这样做，直到堆里没有数字。 最终得到一个空堆和一个排序的数组。
## 例子
1.对数字 1~9 进行排序
2.首先，我们假设最左边的数字 5 已经完成排序，所以此时只有 5 是已归位的数字。
3.接下来，从待排数字(未排序区域)中取出最左边的数字 3，将它与左边已归位的数字进行比较。若左 边的数字更大，就交换这两个数字。重复该操作，直到左边已归位的数字比取出的数字更小，或者取 出的数字已经被移到整个序列的最左边为止。
4.由于 5 > 3，所以交换这两个数字。
5.对数字 3 的操作到此结束。此时 3 和 5 已归位，还剩下右边 7 个数字尚未排序。
6.接下来是第 3 轮。和前面一样，取出未排序区域中最左边的数字 4，将它与左边的数字 5 进行比较。
7.由于 5>4，所以交换这两个数字。交换后再把 4 和左边的 3 进行比较，发现 3<4，因为出现了比自己 小的数字，所以操作结束。
8.于是 4 也归位了。此时 3、4、5 都已归位，已排序区域也得到了扩大。
9.遇到左边的数字都比自己小的情况时......
10.不需要任何操作即可完成排序
11.重复上述操作，直到所有数字都归位
12.对所有数字的操作都结束时，排序也就完成了。
## 代码实现
```swift
func insertionSort(_ arr:[Int]) -> [Int] {
var ret = arr
for x in 1..<ret.count {
var y = x
let tmp = ret[y]
while y > 0 && tmp < ret[y - 1] {
ret[y] = ret[y-1]
y -= 1
}
ret[y] = tmp
}
return ret
}
let arr = [5,8,4,7,9,1,6]
let ret = insertionSort(arr)
```
## 性能
在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一 样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换 数字的位置。
然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换 数字，直到它到达整个序列的最左边为止。具体来说，就是第 k 轮需要比较 k - 1 次。因 此，在最糟糕的情况下，第 2 轮需要操作 1 次，第 3 轮操作 2 次......第 n 轮操作 n -1 次，所以时间复杂度和冒泡排序的一样，都为 O(n^2)。
输入数据按从大到小的顺序排列时就是最糟糕的情况。