投稿    登录
欢迎来访~

浅谈排序算法与优化(仅部分,Updating)

Other Payne 840浏览 0评论

扫码或搜索:进击的Coder

发送

即可立即永久解锁本站全部文章

浅谈排序算法与优化(仅部分,Updating)

欢迎查阅与star的源码
**写在最前面,此文章少了各排序算法的对比,但多了一份由浅入深的个人理解,以及代码、及算法的优化的思路**
**阅读文章约 需 5min**

列表排序

排序

将一组“无序”的记录序列调整为“有序”的记录序列

列表排序

将无序的列表变为有序列表

输入:列表;

输出:有序列表

升序与降序

内置排序函数:sort(),基于timsort排序算法

Timsort是一种混合稳定排序算法,源自归并排序(merge sort)和插入排序(insertion sort)

有兴趣的伙计可以看看这两篇文章

sort算法运用原理1

sort算法运用原理2

TimSort

常见排序算法

LOW:

冒泡:

列表每两个相邻的数,如果前面比后面大,则交换这两个数

一趟排序完成后,则无序区减少一个数,有序区增加一个数

Runtime

优化:

在一次回头看看冒泡排序具体实现思路,将列表每两个相邻的数,如果前面比后面大,则交换这两个数,一趟排序完成后,则无序区减少一个数,有序区增加一个数

如果无序区已经是有序的呢?按照代码执行流程可知,

如果前者比后者大,那么则两个交换位置。(假设为降序,前面为无序区,后面为有序区)

否则不执行任何交换操作,但会执行便利(也可以理解为此运算”不执行任何交换操作,无实际意义”)

优化目标:(将“不执行任何交换的操作去掉”),咱们在回头看看,具体实际的运算是在第二层for循环里面的,也就说所谓的“无用功”也是在这里产生的

无用功体现为:无论是否进行了位置交换,都会在往有序区在遍历检查一遍

思路如下:

主要优化的地方在跳出循环,在它不交换位置的时候,直接跳出此次的循环

假设它全部都是有序的,并设个标记True,

当如果循环内发生了位置交换,则改变标记为False。

流程控制,if。当if True的时则会执行if内部代码(设立return,或者break)主要跳出循环。避免对有序区进行有一次的排序操作

具体代码实现如下:

选择:

插入:

Stronger

快速排序:

堆排序

归并排序

其他排序:

希尔排序

计数排序

基数排序

选择:

插入:

Stronger

快速排序:

堆排序

归并排序

其他排序:

希尔排序

计数排序

基数排序

转载请注明:静觅 » 浅谈排序算法与优化(仅部分,Updating)

更多文章、联系博主、技术交流、商务合作

扫码或搜索:进击的Coder

进击的Coder

微信公众号 扫一扫关注

喜欢 (24)or分享 (0)

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址