Python|理解折半插入排序

引言

插入排序中有直接插入排序,善于思考的能够发现该算法在进插入的时候是采用了顺序查找的方法,而在要查找的表中数据本身有序的前提下可以使用折半查找来代替顺序查找,这种排序的算法就是折半插入排序算法。

算法描述

本篇文章描述的是折半插入排序算法,折半插入排序算法的原理就是利用折半查找的方法来查找插入的位置,然后直接将需要的数据插入该位置就可以了。

第一步:先将需要排序的序列中的第一个数据看成是一个有序序列。

第二步:从第二个元素开始,逐个进行插入。

第三步:在插入的时候先使用折半查找在有序序列中找到该数据应该插入的位置,比较该数据与有序序列中的中间值大小。

给定一个序列为a[0], a[1], a[2]……a[i-1], a[i], a[i+1]……a[n-1]。假设前面i个元素已经是有序序列,现在将第i个元素插入其中,首先需要做的是找到插入元素的位置,然后再插入。

此时定义两个指针为low和high,low指向a[0],high指向a[i-1],使用折半查找,前面有序序列的中间值为a[mid],mid=(low+high)/2,则前面序列为a[0], a[1], a[2]…a[mid]…a[i-1]。将a[i]与a[mid]进行比较,若a[i]>a[mid] ,说明a[i]的位置就应该在mid和high之间,再在mid和high之间用相同方法进行查找。若a[i]< a[mid], 说明a[i]的位置就应该在mid和low之间,再在mid和low之间用相同方法进行查找。找到相应位置后就将该数据插入到该位置,这样就进行了一次折半插入排序。

例题:给定序列[5,2,6,0,9],对其进行排序

首先把5当成有序序列

1.此时mid为5,将2与5做比较,2比5小,插在5前面

则为[2,5, 6,0,9]

2.将6先与2比较,再与6比较得

[2,5, 6,0,9]

3.将0先与5作比较,比5小,则位置在5左边,再与2比较,比2小,则再2左边。

[0,2,5, 6, 9]

最后结果为[0,2,5, 6, 9]。

结语

以上就是对折半插入排序的简单讲解,其中需要注意的就是:在进行折半查找的时候要在有序序列中进行查找;折半查找是查找数据对有序序列的中间值进行比较。

主编:欧洋

稿件来源:深度学习与文旅应用实验室(DLETA)

(0)

相关推荐

  • 西门子PLC:通过指针轻松实现多个数据排列

    关注"PLC发烧友",一起涨知识! 在PLC编程时,经常会使用多个数据,在这些数据中找到想要的数据就变得非常困难了.就像我们在茫茫人海中要寻找那个"她",该去哪 ...

  • Go 数据结构和算法篇(九):二分查找

    今天 以下文章来源于xueyuanjun ,作者xueyuanjun 介绍完基本的线性表排序算法后,今天我们来介绍一种常见的线性表查找算法 -- 二分查找. 一.二分查找的引入 对于基于数字索引的数组 ...

  • 快速排序

    快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要 ...

  • Python|关于简单插入排序的奥秘

    前言 相信大家在生活中经常会遇到排序的问题,比如,如果你是超市工作人员,看到货架上的货品被顾客弄乱了,你一定会重新给货品排序,基本上是按从小到大.从矮到高的顺序摆放.在家里面,你也一定会给家里的物品按 ...

  • Python理解函数调用的原理及其概念

    本文将介绍与函数有关的所有概念,并让你很容易理解.这个主题很容易理解,但是由于实践经验较少而很难理解. 涉及的主题: 介绍 函数参数及其类型 全局和局部变量 将数据序列传递给功能 匿名函数-Lambd ...

  • 关于python中if __name__ == '__main__':的理解

    调试代码的时候都会写上if __name__ == '__main__':,然后写上数据进行调试,一直没有理解到这句的含义,就照搬着写,到现在才算理解到,大概说下自己的见解. 1.在python里__ ...

  • 如何理解Python之禅著名的格言:显式胜于隐式?

    作者:三点水 来源:https://lotabout.me/2021/Explicit-is-Better-than-implicit "Explicit is better than im ...

  • 理解Python多线程:通过易懂的小例子展开

    4天前 1 默认启动主线程 一般的,程序默认执行只在一个线程,这个线程称为主线程,例子演示如下: 导入线程相关的模块 threading: import threading threading的类方法 ...

  • 理解 asyncio 来构建高性能 Python 网络程序

    Python 是一门上手快.优雅简洁的编程语言,其多范式.丰富的标准库和第三方库能够让编程人员把精力集中在逻辑和思维方法上,而不用去担心复杂语法.类型系统等外在因素,从而高效地达成自己的编程目标.Py ...

  • 【Python 成长之路】快速理解复制、浅拷贝、深拷贝

    [本文已由 鹏哥贼优秀 授权转载(原创)作者:鹏哥贼优秀] 1. 示例代码 在进行示例代码展示前,我们先理解下什么叫 复制.浅拷贝.深拷贝. [直接赋值]:其实就是对象的引用(别名). [浅拷贝 (c ...

  • 基于Python的自动化测试平台开发你要理解的:uWSGI

    在我们使用Django开发自动化测试平台时,最必不可少的步骤是在服务器上部署它.在开发阶段中,对于Django项目我们使用的web服务器一般都是自带的runserver, 但是runserver从内存 ...

  • 深入理解 Python 内部函数和闭包(进阶)

    大家好,我是安果! 本文以内部函数为主线,深入讲解内部函数和闭包的应用场景和原理,学会后你的 Python 水平会再上一个台阶,对工作面试或实战应用都会很有帮助 本文包括: 函数是一等公民 内部函数定 ...