3. 插入排序（简单插入排序）
3.1算法思想
如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、长度增加1的有序数据。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
同样，这个算法不需要额外的存储空间，空间复杂度为o（1），时间复杂度为o（n^2）
3.2算法过程
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。直到排完序为止。
3.3 python实现
def
insertionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
preIndex
=
i
-
1
current
=
numList
[
i
]
while
preIndex
>=
0
and
current
<
numList
[
preIndex
]
:
numList
[
preIndex
+
1
]
=
numList
[
preIndex
]
preIndex
-=
1
numList
[
preIndex
+
1
]
=
current
return
numList
numlist
=
[
5
,
3
,
2
,
1
,
6
,
8
,
4
,
2
,
6
]
print
(
insertionSort
(
numlist
)
)
# 输出结果为：[1, 2, 2, 3, 4, 5, 6, 6, 8]
