Python插入排序和堆排序，python排序堆排序,插入排序，它的工作原理是

Python插入排序和堆排序，python排序堆排序,插入排序，它的工作原理是

插入排序，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

 def insertion_sort(list2):     for i in range(1, len(list2)):         save = list2[i]         j = i         while j > 0 and list2[j - 1] > save:             list2[j] = list2[j - 1]             j -= 1         list2[j] = save

堆排序：是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父节点。

 def heap_sort(list2):     first = 0     last = len(list2) - 1     create_heap(list2, first, last)     for i in range(last, first, -1):         list2[i], list2[first] = list2[first], list2[i]  # swap         establish_heap_property (list2, first, i - 1) # create heap (used by heap_sort) def create_heap(list2, first, last):     i = last/2     while i >= first:         establish_heap_property(list2, i, last)         i -= 1 # establish heap property (used by create_heap) def establish_heap_property(list2, first, last):     while 2 * first + 1 <= last:         k = 2 * first + 1         if k < last and list2[k] < list2[k + 1]:             k += 1         if list2[first] >= list2[k]:             break         list2[first], list2[k] = list2[k], list2[first]  # swap         first = k

执行程序：

 >>> lst2=[6,7,4,3,0,9] >>> heap_sort(lst2) >>> lst2 [0, 3, 4, 6, 7, 9] >>> lst3 = [5,8,0,9,1,4] >>> heap_sort(lst3) >>> lst3 [0, 1, 4, 5, 8, 9]