Python 插入排序

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

实例

definsertionSort(arr):         foriinrange(1, len(arr)):             key = arr[i]             j = i-1        whilej >=0andkey < arr[j] :                  arr[j+1] = arr[j]                  j -= 1        arr[j+1] = key       arr = [12, 11, 13, 5, 6]insertionSort(arr)print("排序后的数组:")foriinrange(len(arr)):      print("%d" %arr[i])

执行以上代码输出结果为：

排序后的数组:

5

6

11

12

13

主函数迭代次数：数值个数n 0.5n(n + 1)。

"""插入排序

InsertionSort.py"""

# 一次往数组添加多个数字

def AppendNumbers(array):

   num = input('Numbers:(split by spaces)\t').split()

   for i in num:

       array.append(int(i))

   print('排序前数组：{}.'.format(array))

def InsertionSort(array):

   AppendNumbers(array)  # 添加

   list = []

   while True:

       for i in array:

           minimum = min(array)

           if i == minimum:

               list.append(i)

               array.remove(i)  # 删去最小值

       if array == []:

           break

   print('排序后数组：{}.'.format(list))

array = [6, 4, 45, -2, -1, 2, 4, 0, 1, 2, 3, 4, 5, 6, -4, -6,  7, 8, 8, 34, 0]

InsertionSort(array)