• 欢迎来到本博客,希望可以y一起学习与分享

排序算法

笔记 benz 5个月前 (05-11) 10次浏览 0个评论 扫描二维码
文章目录[隐藏]

如何选择合适的排序算法?

如果要实现一个通用的高效率的排序函数,我们应该选择那种排序算法呢?各种排序算法的特点如下所示:

  • 线性排序算法的时间复杂度比较低,适用场景特殊,因此不适合作为通用的排序函数。
  • 小规模数据可以选择时间复杂度为 O(n²) 的算法,大规模数据选择时间复杂度为 O(nlogn) 的算法则会更加高效。为了兼顾任意规模的数据,一般会首选复杂度为 O(nlogn) 的算法来实现排序函数。
  • 归并排序虽然最好情况、最坏情况和平均情况下时间复杂度都可以做到 O(nlogn),但它不是原地排序算法,空间复杂度为 O(n),排序的时候需要的额外空间和源数据一般大,空间消耗过高。

冒泡

$i只负责计数层数,最后一层是不需要操作的,因为arr[$j]与arr[$j+1]比较的时候就排好了,所以$len-1;
$j指的是数组的下标,每次都需要从arr[0]开始,因为$j+1=$len-$i,所以$j=$len-$i-1;

 

快排

双路快排


三路快排

当面对有大量重复元素的数据时,还是有可能退化成O(n^2)级别的,于是对双路快排进行优化,提出了三路快排。
三路快排要做的事情,其实就是将数组分成三部分:小于v,等于v和大于v,之后递归的对小于v和大于v部分进行排序就好了。

三路快排如此好的解决了近乎有序的数组和有大量重复数组的元素排序问题,以至于在很多语言的标准库中,排序接口使用的就是三路快排的思路,比如Java语言。


三路快排优化

测试

归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

分而治之


文章 排序算法 转载需要注明出处
喜欢 (0)

您必须 登录 才能发表评论!