Python天天美味(31) - python数据结构与算法之插入排序-阿里云开发者社区

Python天天美味(31) - python数据结构与算法之插入排序

2017-01-11 1341

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

1. 直接插入排序

插入排序算法思路是:
假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

def insert_sort ( data ):
     for i in range ( 1 , len ( data )):
         temp = data [ i ]      #data[i] is to insert
         j = i - 1
         while j >= 0 and temp < data [ j ]:
             data [ j + 1 ] = data [ j ]
             j = j - 1
         if j <> i - 1 :
             data [ j + 1 ] = temp       #insert temp

2. 希尔排序

希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。希尔排序基本思想是：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt< dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

def shell_sort ( data , n = None ):
     if n == None :
         n = len ( data ) / 2
         if n % 2 == 0 :
             n = n + 1
     for i in range ( 0 , n ):
         newdata = data [ i : len ( data ): n ]
         insert_sort ( newdata )
         data [ i : len ( data ): n ] = newdata
     if n <> 1 :
         d = n / 2
         if d % 2 == 0 :
             d = d + 1
         shell_sort ( data , d )