常用的排序算法总结 常用排序算法有哪些
yuyutoo 2024-10-12 01:08 1 浏览 0 评论
前言
查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序等基本的排序算法,并且经常有面试官要求现场手写出基本的排序算法。如果这些问题回答不好,估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握,有必要时要熟练写出代码。
今天主要介绍冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序的思想,实现代码全部采用 Python 实现。
准备工作
所谓 “磨刀不误砍柴工”,在进行排序算法练习的时候,我们需要做一些准备的工作:
- 生成算法需要的数列:随机数列
- 对于一些极端情况,考虑算法的效率,需要生成基本有序的数列
- 测试算法性能的函数
- 判断数列是否有序
- 数列中元素相互交换
- 数列的拷贝
生成随机数列
生成基本有序的数列
判断数列是否有序(算法是否正确)
测试算法性能(耗费时间)
数列中元素相互交换
Python 语言对于交换两个数列的元素非常简单:
数列的拷贝
对于数列的拷贝,在python语言中可以直接使用数列的切片
冒泡排序
算法思想
冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项,并且交换顺序排错的项。每对 列表实行一次遍历,就有一个最大项排在了正确的位置。大体上讲,列表的每一个数据项都会在 其相应的位置 “冒泡”。如果列表有n项,第一次遍历就要比较 n-1 对数据。需要注意,一旦列 表中最大(按照规定的原则定义大小)的数据是所比较的数据对中的一个,它就会沿着列表一直 后移,直到这次遍历结束。
动图图示
代码实现
优化点
因为冒泡排序必须要在最终位置找到之前不断交换数据项,所以它经常被认为是最低效的排 序方法。这些“浪费式”的交换操作消耗了许多时间。但是,由于冒泡排序要遍历整个未排好的 部分,它可以做一些大多数排序方法做不到的事。尤其是如果在整个排序过程中没有交换,我们 就可断定列表已经排好。因此可改良冒泡排序,使其在已知列表排好的情况下提前结束。这就是 说,如果一个列表只需要几次遍历就可排好,冒泡排序就占有优势:它可以在发现列表已排好时 立刻结束
优化代码
选择排序
算法思想
选择排序提高了冒泡排序的性能,它每遍历一次列表只交换一次数据,即进行一次遍历时找 到最大的项,完成遍历后,再把它换到正确的位置。和冒泡排序一样,第一次遍历后,最大的数 据项就已归位,第二次遍历使次大项归位。这个过程持续进行,一共需要 n-1 次遍历来排好 n 个数 据,因为最后一个数据必须在第 n-1 次遍历之后才能归位。
动图演示
代码实现
插入排序
算法思想
插入排序的算法复杂度仍然是 O(n^2),但其工作原理稍有不同。它总是保持一个位置靠前的 已排好的子表,然后每一个新的数据项被 “插入” 到前边的子表里,排好的子表增加一项。我们认为只含有一个数据项的列表是已经排好的。每排后面一个数据(从1开始到 n-1),这 个的数据会和已排好子表中的数据比较。比较时,我们把之前已经排好的列表中比这个数据大的移到它的右边。当子表数据小于当前数据,或者当前数据已经和子表的所有数据比较了时,就可 以在此处插入当前数据项。
动图演示
代码实现
注意:这里在用 Python 实现的时候需要注意,第一次我采用的是下面的代码:
在测试性能的时候发现,当数列的逐渐变大的时候,运行时间并不是按照 n^2 的速度增长,后来分析发现:
这行代码在数列很大的时候,会不听的新建列表,这回损害性能,这是非算法思想因素的影响,但是需要注意一下。
希尔排序
算法思想
希尔排序有时又叫做 “缩小间隔排序”,它以插入排序为基础,将原来要排序的列表划分为一些子列表,再对每一个子列表执行插入排序,从而实现对插入排序性能的改进。划分子列的特定方法是希尔排序的关键。我们并不是将原始列表分成含有连续元素的子列,而是确定一个划分列表的增量 “i”,这个i更准确地说,是划分的间隔。然后把每间隔为i的所有元素选出来组成子列表,然后对每个子序列进行插入排序,最后当 i=1 时,对整体进行一次直接插入排序
动图演示
代码实现
归并排序
算法思想
归并排序是一种递归算法,它持续地将一个列表分成两半。如果列表是空的或者 只有一个元素,那么根据定义,它就被排序好了(最基本的情况)。如果列表里的元素超过一个,我们就把列表拆分,然后分别对两个部分调用递归排序。一旦这两个部分被排序好了,然后就可以对这两部分数列进行归并了。归并是这样一个过程:把两个排序好了的列表结合在一起组合成一个单一的有序的新列表。有自顶向下(递归法)和自底向上的两种实现方法。
动图演示
自顶向下(递归法)方法实现
注意:这里进行小的优化,当数列的长度小于等于15的时候,我们一般认为数列此时基本有序,这时候采用直接插入排序非常快
自底向上(非递归法)方法
快速排序
算法思想
快速排序由 C. A. R. Hoare 在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法步骤
- 从数列中挑出一个元素,称为 "基准"(pivot),
- 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
动图演示
代码实现
快速排序一些可以优化的点
- 当数列近乎有序的时,由于每次选取的都是第一个数,所以造成数列分割的极其不等,此时快排蜕化成 O(n^2) 的算法, 此时只要随机选取基准点即可
- 当数列中包含大量的重复元素的时候,这一版的代码也会造成"分割不等“的问题,此时需要将重复元素均匀的分散的自数列旁
- 使用三路快排
参考资料
- 《数据结构》 严蔚敏 吴伟民 编著
- 《Problem Solving with Algorithms and Data Structures using python》By Brad Miller and David Ranum, Luther College
相关推荐
- jQuery VS AngularJS 你更钟爱哪个?
-
在这一次的Web开发教程中,我会尽力解答有关于jQuery和AngularJS的两个非常常见的问题,即jQuery和AngularJS之间的区别是什么?也就是说jQueryVSAngularJS?...
- Jquery实时校验,指定长度的「负小数」,小数位未满末尾补0
-
在可以输入【负小数】的输入框获取到焦点时,移除千位分隔符,在输入数据时,实时校验输入内容是否正确,失去焦点后,添加千位分隔符格式化数字。同时小数位未满时末尾补0。HTML代码...
- 如何在pbootCMS前台调用自定义表单?pbootCMS自定义调用代码示例
-
要在pbootCMS前台调用自定义表单,您需要在后台创建表单并为其添加字段,然后在前台模板文件中添加相关代码,如提交按钮和表单验证代码。您还可以自定义表单数据的存储位置、添加文件上传字段、日期选择器、...
- 编程技巧:Jquery实时验证,指定长度的「负小数」
-
为了保障【负小数】的正确性,做成了通过Jquery,在用户端,实时验证指定长度的【负小数】的方法。HTML代码<inputtype="text"class="forc...
- 一篇文章带你用jquery mobile设计颜色拾取器
-
【一、项目背景】现实生活中,我们经常会遇到配色的问题,这个时候去百度一下RGB表。而RGB表只提供相对于的颜色的RGB值而没有可以验证的模块。我们可以通过jquerymobile去设计颜色的拾取器...
- 编程技巧:Jquery实时验证,指定长度的「正小数」
-
为了保障【正小数】的正确性,做成了通过Jquery,在用户端,实时验证指定长度的【正小数】的方法。HTML做成方法<inputtype="text"class="fo...
- jquery.validate检查数组全部验证
-
问题:html中有多个name[],每个参数都要进行验证是否为空,这个时候直接用required:true话,不能全部验证,只要这个数组中有一个有值就可以通过的。解决方法使用addmethod...
- Vue进阶(幺叁肆):npm查看包版本信息
-
第一种方式npmviewjqueryversions这种方式可以查看npm服务器上所有的...
- layui中使用lay-verify进行条件校验
-
一、layui的校验很简单,主要有以下步骤:1.在form表单内加上class="layui-form"2.在提交按钮上加上lay-submit3.在想要校验的标签,加上lay-...
- jQuery是什么?如何使用? jquery是什么功能组件
-
jQuery于2006年1月由JohnResig在BarCampNYC首次发布。它目前由TimmyWilson领导,并由一组开发人员维护。jQuery是一个JavaScript库,它简化了客户...
- django框架的表单form的理解和用法-9
-
表单呈现...
- jquery对上传文件的检测判断 jquery实现文件上传
-
总体思路:在前端使用jquery对上传文件做部分初步的判断,验证通过的文件利用ajaxFileUpload上传到服务器端,并将文件的存储路径保存到数据库。<asp:FileUploadI...
- Nodejs之MEAN栈开发(四)-- form验证及图片上传
-
这一节增加推荐图书的提交和删除功能,来学习node的form提交以及node的图片上传功能。开始之前需要源码同学可以先在git上fork:https://github.com/stoneniqiu/R...
- 大数据开发基础之JAVA jquery 大数据java实战
-
上一篇我们讲解了JAVAscript的基础知识、特点及基本语法以及组成及基本用途,本期就给大家带来了JAVAweb的第二个知识点jquery,大数据开发基础之JAVAjquery,这是本篇文章的主要...
- 推荐四个开源的jQuery可视化表单设计器
-
jquery开源在线表单拖拉设计器formBuilder(推荐)jQueryformBuilder是一个开源的WEB在线html表单设计器,开发人员可以通过拖拉实现一个可视化的表单。支持表单常用控件...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)