插入排序

主要思想：每轮 从未排序部分取一个元素插入到已经排序好的队列中，保证新的元素插入之后的新队列依旧是有序的。

3.1 简单演示

• 白色背景表示未排序部分
• 灰色背景表示已排序部分
• 砖红色背景指示其是本轮待插入的目标元素
• 淡黄色背景指示目标元素此次要对比的元素（淡换色背景的元素是上一轮排序的元素）

• 初始状态

  insert-sort-base.png
  • 初始状态有n=7个元素，初始时，第一个元素属于已经排好序的元素，所以 第一轮需要将第二个元素插入到一排序的序列；

• 第一轮

  insert-sort-first.png

• 第二轮

insert-sort-second.png

• 第三轮

insert-sort-third.png

• 第四轮

  insert-sort-fourth.png

• 第五轮

  insert-sort-fifth.png

• 第六轮

  insert-sort-sixth.png

3.2 实现分析

对于一个长度位n的待排序数组A，我们作如下分析：

• 根据上面的演示分析，对于一个长度为n的数组，我们需要n-1轮对其排好序；

  => 在代码实现部分，轮数对应于第一个for循环：

  # 由于选择排序很直观就是一个从左往右的过程，所以一般第一个for循环都是正向遍历
  for i in range(1, n)
  

• 对于第 i 轮，我们需要将下标为 i 的元素插入到 A[0 : i - 1] 组成的有序列表当中，具体表示如下（核心就是：每次都和当前元素左边的元素比较，如果左边元素比当前元素大，就交换，直到遇到小于等于自己的元素，跳出第二层循环）：

  for i in range(1, n):
      curIndex = i
      for j in range(curIndex - 1, -1, -1):
          if A[j] > A[curIndex]:
              A[j], A[curIndex], curIndex = A[curIndex], A[j], j
          else:
            break
  

3.3 实现

这个实现就和冒泡很像了，但是与冒泡相比，我们始终用一个下标跟踪我们当前要插入的元素

def insertSort(A):
    n = len(A)
    for i in range(1, n):
        curIndex = i
        for j in range(curIndex - 1, -1, -1):
            if A[j] > A[curIndex]:
                A[j], A[curIndex], curIndex = A[curIndex], A[j], j
            else:
                break


if __name__ == '__main__':
    A = [5, 7, 1, 3, 6, 2, 4]
    insertSort(A)
    print(A, "= [1, 2, 3, 4, 5, 6, 7]")