排序之插入排序
2018 algorithm插入排序就是构建有序序列,对于未排序的下一个数据,在已排序序列中从后往前扫描,找到合适的位置插入。
图片来源:维基百科
- 插入排序是一种稳定的排序方法。
- 插入排序的时间复杂度为 O(n2)。
- 插入排序的空间复杂度为 O(1)。
插入排序跟选择排序很相似。
插入排序是从选择下一个元素,然后在已经排序好的序列中从后往前遍历,插入到合适的位置。
选择排序是从选择下一个位置,然后从该位置的元素从前往后遍历,选择最小的值排序。
插入排序的伪代码:
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while