【python 谢尔排序算法】

2024-01-27 09:20
文章标签 python 算法 排序 谢尔

本文主要是介绍【python 谢尔排序算法】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【python & 谢尔排序算法】

  • 算法基本原理思想
    • 简单排序代码示例
      • 复杂度分析

算法基本原理思想

注意到插入排序的比对次数,在最好的情况下是0(n),这种情况发生在列表已是有序的情况下,实际上,列表越接近有序,插入排序的比对次数就越少;从这个情况入手,谢尔排序以插入排序作为基础对无序表进行“间隔”划分子列表,每个子列表都执行插入排序

  • 随着子列表的数量越来越少,无序表的整体越来越接近有序从而减少整体排序的比对次数

  • 间隔为3的子列表,子列表分别插入排序后的整体状况更接近有序
    在这里插入图片描述
    在这里插入图片描述

  • 最后一趟是标准的插入排序,但由于前面几趟已经将列表处理到接近有序,这一趟仅需少数几次移动即可完成

在这里插入图片描述

  • 子列表的间隔一般从n/2开始,每趟倍增:n/4,n/8……直到1个
    在这里插入图片描述

简单排序代码示例


'''
@ time :2021年10月22日
@ author : wupke
@ description: 谢尔排序算法
'''import time# # #    
start1 = time.clock()def shellSort(alist):# 设定子列表间隔sublistcount = len(alist)//2while sublistcount > 0:# 子列表排序for startposition in range (sublistcount):gapInsertionSort(alist,startposition,sublistcount)print("after increments of size",sublistcount,"the list is",alist)# 再次缩小间隔sublistcount = sublistcount//2# 插入排序
def gapInsertionSort(alist,start,gap):for  i in range(start+gap, len(alist),gap):# gap 是步长,新插入项currentvalue = alist[i]position = iwhile position >= gap and alist[position-gap]>currentvalue:# 对比,移动alist[position] = alist[position-gap]position = position-gap#插入新项alist[position]=currentvaluealist = [22,33,44,55,21,31,45,76,88,54,3,5,7,2]
shellSort(alist)
end1 = time.clock()
print("%s排序用时%s" %(alist,(end1-start1)))

复杂度分析

  • 粗看上去,谢尔排序以插入排序为基础,可能并不会比插入排序好
  • 但由于每趟都使得列表更加接近有序,这过程会减少很多原先需要的“无效”比对对谢尔排序的详尽分析比较复杂,大致说是介于0(n)和0(n2)之间。
    在这里插入图片描述

这篇关于【python 谢尔排序算法】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/649799

相关文章

Python多重继承慎用的地方

《Python多重继承慎用的地方》多重继承也可能导致一些问题,本文主要介绍了Python多重继承慎用的地方,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录前言多重继承要慎用Mixin模式最后前言在python中,多重继承是一种强大的功能,它允许一个

python+OpenCV反投影图像的实现示例详解

《python+OpenCV反投影图像的实现示例详解》:本文主要介绍python+OpenCV反投影图像的实现示例详解,本文通过实例代码图文并茂的形式给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前言二、什么是反投影图像三、反投影图像的概念四、反向投影的工作原理一、利用反向投影backproj

Python中edge-tts实现便捷语音合成

《Python中edge-tts实现便捷语音合成》edge-tts是一个功能强大的Python库,支持多种语言和声音选项,本文主要介绍了Python中edge-tts实现便捷语音合成,具有一定的参考价... 目录安装与环境设置文本转语音查找音色更改语音参数生成音频与字幕总结edge-tts 是一个功能强大的

使用Python和PaddleOCR实现图文识别的代码和步骤

《使用Python和PaddleOCR实现图文识别的代码和步骤》在当今数字化时代,图文识别技术的应用越来越广泛,如文档数字化、信息提取等,PaddleOCR是百度开源的一款强大的OCR工具包,它集成了... 目录一、引言二、环境准备2.1 安装 python2.2 安装 PaddlePaddle2.3 安装

Python+PyQt5开发一个Windows电脑启动项管理神器

《Python+PyQt5开发一个Windows电脑启动项管理神器》:本文主要介绍如何使用PyQt5开发一款颜值与功能并存的Windows启动项管理工具,不仅能查看/删除现有启动项,还能智能添加新... 目录开篇:为什么我们需要启动项管理工具功能全景图核心技术解析1. Windows注册表操作2. 启动文件

Python datetime 模块概述及应用场景

《Pythondatetime模块概述及应用场景》Python的datetime模块是标准库中用于处理日期和时间的核心模块,本文给大家介绍Pythondatetime模块概述及应用场景,感兴趣的朋... 目录一、python datetime 模块概述二、datetime 模块核心类解析三、日期时间格式化与

Java调用Python的四种方法小结

《Java调用Python的四种方法小结》在现代开发中,结合不同编程语言的优势往往能达到事半功倍的效果,本文将详细介绍四种在Java中调用Python的方法,并推荐一种最常用且实用的方法,希望对大家有... 目录一、在Java类中直接执行python语句二、在Java中直接调用Python脚本三、使用Run

使用Python开发Markdown兼容公式格式转换工具

《使用Python开发Markdown兼容公式格式转换工具》在技术写作中我们经常遇到公式格式问题,例如MathML无法显示,LaTeX格式错乱等,所以本文我们将使用Python开发Markdown兼容... 目录一、工具背景二、环境配置(Windows 10/11)1. 创建conda环境2. 获取XSLT

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-