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

开发者社区> zting科技> 正文

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

简介:
+关注继续查看

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)


3. 性能比较

对2000个随机数进行排序,比较直接插入排序、希尔排序、快速排序、冒泡排序的性能,结果如下 :

shell_sort 0:00:00.110000
insert_sort 0:00:01.391000
quick_sort 0:00:00.047000
bubble_sort 0:00:03.438000


性能排名如下:
快速排序 > 希尔排序 > 直接插入排序 > 冒泡排序

 

Python 天天美味系列(总)   

Python 天天美味(29) - 调用VC++的动态链接库(DLL) 

Python 天天美味(30) - python数据结构与算法之快速排序 

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

Python 天天美味(32) - python数据结构与算法之堆排序 

Python 天天美味(33) - 五分钟理解元类(Metaclasses)[转]

... 

  


本文转自CoderZh博客园博客,原文链接:http://www.cnblogs.com/coderzh/archive/2008/09/21/1295434.html,如需转载请自行联系原作者


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

相关文章
算法-插入排序算法
如果输入数组已经是排好序的话,插入排序出现最佳情况。其时间代价是O(n)。 如果输入数组是逆序排列的,将出现最坏情况。 平均情况与最坏情况一样,其时间代价是 O(N^2)。
5 0
python实现选择排序算法
选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。 完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。
1196 0
小记 用python进行排序
Linux 中可以使用 sort 进行排序,python中也一样,那么怎样实现把一个数字的 list 从小到大排序,然后写入文件,然后从文件中读取出来文件内容,然后反序,再追加到文件的下一行中呢? 思路如下: 1、取一个列表内容 2、对列表内容使用 sort 进行排序,并打...
767 0
python实现希尔排序算法
希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1146 0
【排序算法】插入排序
<p></p> <pre><span style="font-family:KaiTi_GB2312; font-size:18px"><span> </span>本篇博客的主要内容是插入排序。常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希尔排序。这里介绍两个,直接插入排序和希尔排序。 <span> </span>在介绍排序算法时,我将从基本思想、实例讲解、代码理解三个方
932 0
《数据结构与算法:Python语言描述》一导读
由于Python语言的一些优点,近年来,国外已经有不少大学采用它作为第一门计算机科学技术课程的教学语言,包括许多一流大学。国内院校也可能参考这种趋势,出现这种变化。作者在北京大学数学学院开设了基于Python语言的程序设计和数据结构课程,通过亲身实践,发现用Python讲授这两门课程也是一种很好的安排。
1615 0
【算法导论】插入排序法
插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.
899 0
算法研究之插入排序、冒泡排序
1、插入排序:插入是比较简单的一种排序方法,基本思想就是把数据分组两段,一部分是有序,另一部分是待排序的。把有序的数据不断的加大到全数组完成排序。 从左到右将有序数组逐渐增大。 public class Sort { public void insertSort(int[] arrays) { for (int i = 0; i < arrays.
591 0
+关注
3550
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载