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]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
