【码了么】python实现排序（二）-Python实现五大常用排序算法（插入排序）

智一面的面试题提供python的测试题

使用地址：http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9

三、插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1.过程图解

2.算法思想

1. 从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面

2. 然后选择第三个元素，重复上述操作，进行插入

3. 依次选择到最后一个元素，插入后即完成所有排序

3.代码实现

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

4.算法分析

插入排序的适用场景：一个新元素需要插入到一组已经是有序的数组中，或者是一组基本有序的数组排序。

1. 比较性：排序时元素之间需要比较，所以为比较排序

2. 稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素才会往后移动，所以相同元素是不会改变相对顺序

3. 时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂度也为O(n^2)

4. 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

5. 记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，再将书插入