搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 记录世界 from antonio > 希尔排序、归并排序、快速排序,KMP

希尔排序、归并排序、快速排序,KMP

记录世界 from antonio 2020-07-01


再说这三种排序前,先对比下这几种排序的复杂度。

希尔排序、归并排序、快速排序,KMP


1.希尔排序

希尔排序的思想是以分组的方式,分而治之。

核心思想:一边分组一边排

希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


例如把10个数据,分为5组,5组里面,小的放在左边,大的放在右边。第二次,再把它分为4组,依然是小的放左边,大的放在右边。分组的次数越多,交换的次数越小。也可以把希尔排序看作一次分组的插入排序。

希尔排序空间存储比较小o(1),适合空间复杂度比较小的场景。如果空间复杂度比较大,一般都是外排序。

稳定和不稳定的意思是什么?

比如集合中,有2个数一样,但是两个数经过排序后,依然顺序不变,这就是稳定性,否则就是不稳定。最好情况和最坏情况不一样。

2.归并排序

核心思想:先分组,再合并排序。

归并排序(采用了递归的思想):归并排序,特殊的地方就是,需要记住前后游标的位置。其它只要记住数据集合和长度就可以。

把一个集合逐级分组,具体如下。

1. 先把集合中的元素,分为2部分。

2. 然后再上面2分的基础,再分为4部分。

3.直到每个集合里面只有2个元素时,进行排序。

4. 排序完后,然后再合并到一起。

希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


归并排序测试:

希尔排序、归并排序、快速排序,KMP


3.快速排序

核心思想:一轮游确定哨兵,哨兵分两边,两边再递归

1. data[i],就只是一个移动的哨兵。如果data[j]对应的值比data[i]大,则j往后移动,反之i往前移动,并实现交换。

2.当i和j相等的时候,哨兵的位置就确定下来了。

3. 经过步骤2的比较,再分成最后两个集合递归执行。

希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


希尔排序、归并排序、快速排序,KMP


快速排序测试:

希尔排序、归并排序、快速排序,KMP


4.KMP算法

如果给定字符串ABCABD。

寻找子串。

希尔排序、归并排序、快速排序,KMP


详细剖析:

左侧是前缀,右侧是后缀,观察前缀和后缀公共元素的个数。

希尔排序、归并排序、快速排序,KMP


pattern是给定的字符串。

希尔排序、归并排序、快速排序,KMP

希尔排序、归并排序、快速排序,KMP




kmp有个回溯的功能,就是用一个数组去存储公共资源的相同部分的数量,把这个数量就依次存储到数组里面。这个数组,是用作回溯用的。这个数组的目的是如果pattern中有重复字符,那么在查找的时候,前面已经比较过的相同字符就无需再对比,进而寻找到最大子串。

希尔排序、归并排序、快速排序,KMP


欢迎关注头条号


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《希尔排序、归并排序、快速排序,KMP》的版权归原作者「记录世界 from antonio」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注记录世界 from antonio微信公众号

记录世界 from antonio微信公众号:antonio_qaa

记录世界 from antonio

手机扫描上方二维码即可关注记录世界 from antonio微信公众号

记录世界 from antonio最新文章

精品公众号随机推荐