插入排序
插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中,左侧的数据 陆续归位,而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据,然后将它插入到已排序区域内合适的位置上。
# 工作原理
- 把一系列数字放在一个未排序的堆里。
- 从堆中挑选一个数字。 你选择哪一个并不重要,但从堆顶挑选是最容易。
- 把这个数插入一个新的数组。
- 从未排序堆中再选择一个数字,并将其插入之前的数组中。 这个数字在第一个数字之前或之后,所以现在这两个数字被排序。
- 再从堆中选择一个数字,并将其插入到数组中的正确排序位置
- 继续这样做,直到堆里没有数字。 最终得到一个空堆和一个排序的数组。
# 例子
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.对所有数字的操作都结束时,排序也就完成了。
# 代码实现
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)。
输入数据按从大到小的顺序排列时就是最糟糕的情况。