插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

 1 def insert_sort(alist):
 2     n = len(alist)
 3     for j in range(1,n):
 4         i = j   
 5         while i > 0:#和有序表中的每个一样元素进行比较（从最后一个开始）
 6             if alist[i] < alist[i-1]:
 7                 alist[i],alist[i-1] = alist[i-1],alist[i]
 8             else:
 9                 break
10             i -= 1
11 if __name__ == '__main__':
12     alist = [54,334,56,65,92,28,68,71,3,34]
13     print('原数组：',alist)
14     insert_sort(alist)
15     print('现数组:',alist)

1 原数组： [54, 334, 56, 65, 92, 28, 68, 71, 3, 34]
2 现数组: [3, 28, 34, 54, 56, 65, 68, 71, 92, 334]

最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)

稳定性：稳定

正是江南好风景