1793: 插入排序

对于未排序第K个元素，在已排序序列中从后向前扫描，找到相应位置并插入。

它的基本方法是：

  （1）从第一个元素开始，该元素可以认为已经被排序；

  （2）取出第K个元素素，在已排序的元素中从后向前扫描；

  （3）如果该元素（已排序）大于第K个元素，将该元素移到下一位置；

  （4）重复步骤3，直到找到已排序的元素小于或者等于第K个元素的位置；

  （5）将第K个元素插入到该位置后面；若找不到小于等于第K个元素位置，就将原来第K个元素插入到数组的首地址。

  重复步骤2~5。

带排序的数组

3 5 6 1 7 9 2 4 8

Pytho可以使用来输入行
num = [int(n) for n in input().split()]

排序后的结果

1 2 3 4 5 6 7 8 9

3 5 6 1 7 9 2 4 8

1 2 3 4 5 6 7 8