几句话描述简单算法——排序与搜索
一、排序
1)桶排序
准备大量的木桶,用木桶的标号(数组下标)作为数据,按照木桶标号的顺序进行排序。
2)选择排序
从“待排序部分”找到最小值(或最大值),让“待排序部分”的起始位置向后移动。
3)冒泡排序
比较相邻的两个数据,把这两个数据按照大小关系正确的交换排列。
4)插入排序
不断地把数据插入已排序的部分数据列,里面恰当的位置。
5)归并排序
分两步走,先了解下归并的概念。归并:把“几个已排序的数据列”合并成“一个已排序的数据列”。
归并排序由分割和归并两个构成。
6)希尔排序
希尔排序就是把数据以一定的间隔进行分组,并且对每个组进行的排序。
7)快速排序
从数据列中任意取出一个值P(基准值),再把“>P”和“<P”的值分离出来,得到新的数据列,P在数据列中的最终位置就确定了。
二、搜索
1)线性搜索
线性搜索就是从起始数据开始,按顺序排除,比较每个数据是否与目标数据一致。
2)二分搜索
二分搜索的前置条件是数据列已经排好序。
二分搜索专注数据列中间位置M1,将数据列分为左右部分,如果数据一致就结束;否则缩小范围,在左边或右边数据列重复查找中间位置M2等,直到结束。
3)哈希搜索
1. 创建哈希表,利用哈希函数求得一个哈希值,将哈希值作为下标。
2. 哈希冲突,很有可能会出现哈希值相同,则可以在哈希值中保存一个单项列表(PHP中可以用Array)。
3. 通过哈希值限定到特定的分组里,实现高效搜索。
4)字符串搜索
“子字符串是数组(多个数据)”,将子字符串的每个字符和目标字符串中的字符一一比较,如果不匹配,重新匹配,下一次开始匹配的位置,就是在当前位置后移一位。
5)KMP搜索
KMP算法可以根据子字符串出现不匹配的位置,决定下一次开始比较字符的位置。
6)BM搜索
BM算法从子字符串的末尾字符开始匹配,根据不匹配的字符和位置信息,决定下一次匹配开始的位置。
参考资料:
相关文章
- 结构建模设计——Solidworks软件之装配体操作基本总结一(装配体功能界面简介、插入零件操作、基本配合操作)
- 程序员如何准备好一次面试
- 面试问到DCL失效不知所措
- Kafka大厂高频面试题:在保证高性能、高吞吐的同时保证高可用性
- 域渗透-横向移动命令总结
- PHP程序员面试时经常会被考的冒泡排序算法
- Spring框架学习笔记(2)——面向切面编程AOP
- Jsp学习笔记(2)——页面导航、表单、EL表达式
- ArcGIS QGIS学习二:图层如何只显示需要的部分几何面数据(附最新坐标边界下载全国省市区县乡镇)
- 新开源HTML5单文件网页版ACME客户端,可在线申请Let's Encrypt、ZeroSSL免费HTTPS多域名通配符泛域名SSL/TLS证书(RSA/ECC/ECDSA)
- Java开发桌面程序学习(13)——Javafx多线程 下载功能
- 移动端实现HTML5 mp3录音踩坑指南:系统播放音量变小、一些机型录音断断续续 之 MediaRecorder和AudioWorklet的终极对决
- 最新全国省市区县乡镇街道行政区划数据提取(2022年)
- 24位PCM采样数据转成16位算法,已实现PCM转WAV在线工具源码支持24bits、16bits、8bits
- (已过时)静态集成腾讯TBS X5内核WebView,从微信提取新版30M浏览器内核打包进apk
- HTML5实现DTMF(电话拨号按键信号)解码、编码,代码简单易于移植
- H5录音音频可视化-实时波形频谱绘制、频率直方图
- Java开发桌面程序学习(12)——Javafx 悬浮窗提示 tooltip
- 真实感受一下县比省大不包邮,省市区乡镇多级数据重装上阵
- Java开发桌面程序学习(11)——javafx 鼠标点击,右击,双击