Python排序搜索基本算法之希尔排序实例分析
本文实例讲述了Python排序搜索基本算法之希尔排序。分享给大家供大家参考,具体如下:
希尔排序是插入排序的扩展,通过允许非相邻的元素进行交换来提高执行效率。希尔排序最关键的是选择步长,本程序选用Knuth在1969年提出的步长序列:1 4 13 40 121 364 1093 3280 。。。后一个元素是前一个元素*3+1,非常方便选取,而且效率还不错。代码如下:
#-*- coding: UTF-8 -*- def shellSort(seq): length=len(seq) inc=0 while inc<=length/3: inc=inc*3+1 print(inc) while inc>=1: for i in range(inc,length): tmp=seq[i] for j in range(i,0,-inc): if tmp<seq[j-inc]: seq[j]=seq[j-inc] else: j+=inc break seq[j-inc]=tmp inc//=3 if __name__=='__main__': print("我们测试结果:") seq=[8,6,4,9,7,3,2,-4,0,-100,99] shellSort(seq) print(seq)
运行结果:
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
相关推荐
-
Python实现的桶排序算法示例
本文实例讲述了Python实现的桶排序算法.分享给大家供大家参考,具体如下: 桶排序也叫计数排序,简单来说,就是将数据集里面所有元素按顺序列举出来,然后统计元素出现的次数.最后按顺序输出数据集里面的元素. 但是桶排序非常浪费空间, 比如需要排序的范围在0~2000之间, 需要排序的数是[3,9,4,2000], 同样需要2001个空间 注意: 桶排序不能排序小数 以下为从小到大代码实现 #!/usr/bin/env python # coding:utf-8 def bucketSort(num
-
Python实现桶排序与快速排序算法结合应用示例
本文实例讲述了Python实现桶排序与快速排序算法结合应用的方法.分享给大家供大家参考,具体如下: #-*- coding: UTF-8 -*- import numpy as np from QuickSort import QuickSort def BucketSort(a, n): barrel = {} for i in xrange(0,n): barrel.setdefault(i, []) min = np.min(a) max = np.max(a) for x in a: f
-
Python实现的基数排序算法原理与用法实例分析
本文实例讲述了Python实现的基数排序算法.分享给大家供大家参考,具体如下: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率
-
Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】
本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方
-
Python排序搜索基本算法之插入排序实例分析
本文实例讲述了Python排序搜索基本算法之插入排序.分享给大家供大家参考,具体如下: 插入排序生活中非常常见,打扑克的时候人的本能就在用插入排序:把抽到的一张插入到手上牌的正确位置上.有两种插入排序方法,一种基于比较,另一种基于交换.代码如下: 1.基于比较的插入排序: # coding:utf-8 def insertionSort(seq): length=len(seq) for i in range(1,length): tmp=seq[i] for j in range(i,0,-1
-
python算法学习之基数排序实例
基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法. 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, i): """计数排序,以i
-
Python排序搜索基本算法之选择排序实例分析
本文实例讲述了Python排序搜索基本算法之选择排序.分享给大家供大家参考,具体如下: 选择排序就是第n次把序列中最小的元素排在第n的位置上,一旦排好就是该元素的绝对位置.代码如下: # coding:utf-8 def selectionSort(seq): length=len(seq) for i in range(length): mini=min(seq[i:]) if seq[i]>mini: j=seq.index(mini,i) seq[i],seq[j]=seq[j],seq[
-
Python排序搜索基本算法之冒泡排序实例分析
本文实例讲述了Python排序搜索基本算法之冒泡排序.分享给大家供大家参考,具体如下: 冒泡排序和选择排序类似,也是第n次把最小的元素排在第n的位置上,也是该元素的绝对位置,只是冒泡排序的过程中,其他的元素也逐渐向自己最终位置逼近.代码如下: def bubbleSort(seq): length=len(seq) for i in range(length): for j in range(length-1,i,-1): if seq[j-1]>seq[j]: seq[j-1],seq[j]=
-
Python实现的数据结构与算法之快速排序详解
本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中
-
python算法学习之桶排序算法实例(分块排序)
复制代码 代码如下: # -*- coding: utf-8 -*- def insertion_sort(A): """插入排序,作为桶排序的子排序""" n = len(A) if n <= 1: return A B = [] # 结果列表 for a in A: i = len(B) while i > 0 and B[i-1] > a:
-
python计数排序和基数排序算法实例
一.计数排序 计数排序(Counting sort)是一种稳定的排序算法 算法的步骤如下:找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数,存入数组C的第i项对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K),空间复杂度为O(N+K).当K不是很大时,这是一个很有效的线性排序算法. 以下是测试代
-
python简单实现基数排序算法
本文实例讲述了python简单实现基数排序算法.分享给大家供大家参考.具体实现方法如下: from random import randint def main(): A = [randint(1, 99999999) for _ in xrange(9999)] for k in xrange(8): S = [ [] for _ in xrange(10)] for j in A: S[j / (10 ** k) % 10].append(j) A = [a for b in S for a
随机推荐
- Access使用查询
- 详解Vue2.0里过滤器容易踩到的坑
- vue与TypeScript集成配置最简教程(推荐)
- 用正则表达式 动态创建/增加css style script 兼容IE firefox
- 轻松掌握Java代理模式
- asp.Net JS取母板页控件值的简单方法
- asp.net 需要登陆的网站上下载网页源代码和文件
- navicat中创建存储过程、触发器和使用游标的简单实例(图文)
- nodejs服务搭建教程 nodejs访问本地站点文件
- 用CSS开发时髦的导航栏图例教程
- C++、C语言和JAVA开发的区别
- Python中的列表生成式与生成器学习教程
- Sql Server 分组统计并合计总数及WITH ROLLUP应用
- SQL Server 2008 安装SQLDMO.dll的方法
- oracle数据库中如何处理clob字段方法介绍
- IE6,IE7,IE8下使用Javascript记录光标选中范围(已补全)
- Flash两个上传示例ASP和PHP(原文件下载,包括后台程序)
- C++学习小结之数据类型及转换方式
- 深入解析Java编程中面向字节流的一些应用
- 悬浮对话框Android代码实现