用Python实现插入排序和选择排序！

这篇是我关于用Python实现50个经典算法代码的第一篇文章，主要目的是在自己手写一遍算法之后，在文章中对算法的细节进行总结来加以巩固。

话不多说，让我们从最基本的排序算法开始吧

插入排序

如下图所示，插入排序的实现思路顾名思义，就是 不断地在一个已经是有序的数组中，寻找合适位置并插入新元素 。

Python学习交流群：1004391443，这里有资源共享，技术解答，还有小编从最基础的Python资料到项目实战的学习资料都有整理，希望能帮助你更了解python，学习python。

<tt-image data-tteditor-tag="tteditorTag" contenteditable="false" class="syl1557732873082" data-render-status="finished" data-syl-blot="image" style="box-sizing: border-box; cursor: text; color: rgb(34, 34, 34); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", "Helvetica Neue", Arial, sans-serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: pre-wrap; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial; display: block;"> image

<input class="pgc-img-caption-ipt" placeholder="图片描述(最多50字)" value="" style="box-sizing: border-box; outline: 0px; color: rgb(102, 102, 102); position: absolute; left: 187.5px; transform: translateX(-50%); padding: 6px 7px; max-width: 100%; width: 375px; text-align: center; cursor: text; font-size: 12px; line-height: 1.5; background-color: rgb(255, 255, 255); background-image: none; border: 0px solid rgb(217, 217, 217); border-radius: 4px; transition: all 0.2s cubic-bezier(0.645, 0.045, 0.355, 1) 0s;"></tt-image>

具体实现步骤为：

首先我们把整个数组拆分为有序区间和未排序区间，有序区间在插入排序一开始只有一个元素，就是数组的第一个元素。

接在有序区间之后的一个元素就是准备插入的元素，在图中就是标为绿色的元素，在有序区间内寻找位置并插入。

其寻找逻辑为：从后往前依次进行比较，如果待插入元素大于当前元素，则将待插入元素插入到当前元素的后一位，如果待插入元素小于当前元素，则将当前元素后移一位。不断重复该过程直至到数组的最后一位

其实现的具体代码为：

<pre spellcheck="false" style="box-sizing: border-box; margin: 5px 0px; padding: 5px 10px; border: 0px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-weight: 400; font-stretch: inherit; font-size: 16px; line-height: inherit; font-family: inherit; vertical-align: baseline; cursor: text; counter-reset: list-1 0 list-2 0 list-3 0 list-4 0 list-5 0 list-6 0 list-7 0 list-8 0 list-9 0; background-color: rgb(240, 240, 240); border-radius: 3px; white-space: pre-wrap; color: rgb(34, 34, 34); letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">def insertion_sort(a):
length = len(a)
if length <=1:
return
for i in range(1,length):
j = i-1
value = a[i]
while j >=0:
if a[j]<value:
a[j+1] = value
break
else:
a[j+1] = a[j]
if j == 0:
a[j] = value
j -=1
print(a)
return a
</pre>

时间复杂计算为：我们需要将整个数组遍历一遍，所以这一部分为O(n)，在每一次遍历中都要执行一次插入操作，其时间复杂度为O(n)，所以总时间复杂度为O(n2)

选择排序

选择排序跟插入排序算法类似，都是将数组分为有序区间和未排序区间，区别在于插入排序是将一个新元素插入到有序区间内，而选择排序则是在未排序区间中找到最小元素，并交换到有序区间之后。

<tt-image data-tteditor-tag="tteditorTag" contenteditable="false" class="syl1557732873089" data-render-status="finished" data-syl-blot="image" style="box-sizing: border-box; cursor: text; color: rgb(34, 34, 34); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "WenQuanYi Micro Hei", "Helvetica Neue", Arial, sans-serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: pre-wrap; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial; display: block;"> image

<input class="pgc-img-caption-ipt" placeholder="图片描述(最多50字)" value="" style="box-sizing: border-box; outline: 0px; color: rgb(102, 102, 102); position: absolute; left: 187.5px; transform: translateX(-50%); padding: 6px 7px; max-width: 100%; width: 375px; text-align: center; cursor: text; font-size: 12px; line-height: 1.5; background-color: rgb(255, 255, 255); background-image: none; border: 0px solid rgb(217, 217, 217); border-radius: 4px; transition: all 0.2s cubic-bezier(0.645, 0.045, 0.355, 1) 0s;"></tt-image>

实现代码为：

<pre spellcheck="false" style="box-sizing: border-box; margin: 5px 0px; padding: 5px 10px; border: 0px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-weight: 400; font-stretch: inherit; font-size: 16px; line-height: inherit; font-family: inherit; vertical-align: baseline; cursor: text; counter-reset: list-1 0 list-2 0 list-3 0 list-4 0 list-5 0 list-6 0 list-7 0 list-8 0 list-9 0; background-color: rgb(240, 240, 240); border-radius: 3px; white-space: pre-wrap; color: rgb(34, 34, 34); letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">def selection_sort(a):
length = len(a)
if length <=1:
return
for i in range(0,length-1):
min_value = a[i]
min_index = i
j = i+1
while j<length:
if a[j] < min_value:
min_value = a[j]
min_index = j
j += 1
a[i],a[min_index] = a[min_index],a[i]
return a
</pre>

时间复杂度计算：数组长度为n，一共需要寻找n次最小值，每次寻找最小值都要遍历未排序区间一次，其时间复杂度为O(n)，乘以n次为O(n2)