一、插入排序（Insertion-Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
1、原理
- 从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面
- 然后选择第三个元素，重复上述操作，进行插入
- 依次选择到最后一个元素，插入后即完成所有排序
2、举例
举个例子，假设我现在有一个数列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序，我们来看看使用插入排序的详细步骤：
- 首先第二个元素99和前面的元素11比较，99>11，第一轮完了，列表是 1 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
- 然后，33作为比较元素，和前面的元素99比较，11<33<99交换位置，33插入到11和99之间，列表为 1 [11, 33, 99, 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
- 接着，33<69<99交换位置，列表变为 1 [11, 33, 69, 99, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
- 以此类推，69<77<99,77插入到69和99之间，列表变为 1 [11, 33, 69, 77, 99, 88, 55, 11, 33, 36,39, 66, 44, 22]
- 77<88<99, 88插入到77和99之间，列表变为 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
- 33<55<69<77<88<99,55插入到33和69之间，列表变为 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
- 。。。。。。。
- 最终得到列表 1 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
注：从第二个元素开始，以此和前面的元素比较，找出相应位置插入。
3、特点
插入排序的适用场景：一个新元素需要插入到一组已经是有序的数组中，或者是一组基本有序的数组排序。
- 比较性：排序时元素之间需要比较，所以为比较排序
- 稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素才会往后移动，所以相同元素是不会改变相对顺序
- 时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂度也为O(n^2)
- 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
- 记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，再将书插入
def insertion_sort(arr):
"""插入排序"""
# 第一层for表示循环插入的遍数
for i in range(1, len(arr)):
# 设置当前需要插入的元素
current = arr[i]
# 与当前元素比较的比较元素
pre_index = i - 1
while pre_index >= 0 and arr[pre_index] > current:
# 当比较元素大于当前元素则把比较元素后移
arr[pre_index + 1] = arr[pre_index]
# 往前选择下一个比较元素
pre_index -= 1
# 当比较元素小于当前元素，则将当前元素插入在 其后面
arr[pre_index + 1] = current
return arr
arr = [4,5,6,1,3,2]
print (insertion_sort(arr))
正确的输出内容：
[1, 2, 3, 4, 5, 6]
二、选择排序（Selection sort）
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为：选择排序。
1、原理
（1）设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素找到最小的元素，将它和第一个元素互换。
（2）重复上述操作，我们找出第二小的元素和第二个位置的元素互换，以此类推找出剩余最小元素将它换到前面，即完成排序。
2、举例
举个例子，假设我现在有一个数列需要使用冒泡来排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，
我们来看看使用冒泡的详细步骤：
1、首先11作为比较元素和列表后面的所有元素比较，找到最小的11，并放在第一位，第一轮完了，列表是 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
2、然后，99作为比较元素，和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比较，找到最小的11，和第二位元素99交换位置，即第二轮比较完后，列表为 [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]
3、第三轮比较完，22最小，和第三个元素33交换位置，列表变为 [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]
4、最终得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
注：是一轮比较完后，找出最小的，再交换这个元素和对应轮数位置处的元素位置，每轮只交换一次。二冒泡排序是，没比较一次，就交换一次位置，每轮要交换很多次。回到顶部(go to top)
3、代码
实现思路： 使用双重for循环，内层变量为i， 外层为j，在内层循环中不断的比较相邻的两个值（j, j+1）的大小，如果j+1的值大于j的值，交换两者位置，每循环一次，外层的i增加1，等到i等于(len(arr) – 1)的时候，结束循环。
def selection_sort(arr):
"""选择排序"""
# 第一层for表示循环选择的遍数
for i in range(len(arr) - 1):
# 将起始元素设为最小元素
min_index = i
# 第二层for表示最小元素和后面的元素逐个比较
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标
min_index = j
# 查找一遍后将最小元素与起始元素互换
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
A = [64, 25, 12, 22, 11]
print (selection_sort(A))
正确的输出内容：
[11, 12, 22, 25, 64]
