搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 青城博雅教育科技 > 史上最易理解的快速排序原理详解以及Arrays.sort方法

史上最易理解的快速排序原理详解以及Arrays.sort方法

青城博雅教育科技 2019-11-08

Arrays.sort()方法可以通过源码发现内部使用的是快速排序,然后我们探索一下快速排序的原理

快速排序简介


快速排序是交换排序的一种,交换排序的含义是根据序列中的两个元素关键字的比较结果来交换两个记录在序列中的位置。同时,冒泡排序(时间复杂度为O(n2))作为交换排序中的经典,快速排序也是对冒泡排序的一种改进。

快速排序是所有内部排序算法性能最优的排序算法,但是它是一个不稳定的排序算法。

快速排序步骤


    选择基准元素

    通过一趟排序将待排序的记录分割成独立的两部分,其中一部分比基准元素大,另一部分比基准元素小

    基准元素在其排好序的位置上

    分别对划分好的两部分继续进行快速排序,直到整个序列有序


举个栗子:

我们对序列 9 11 5* 22 18 7 5 36 进行非递减排序

史上最易理解的快速排序原理详解以及Arrays.sort方法

快速排序性能分析


平均时间为Tavg(n) = kn ln n,其中n为待排序序列中记录的个数,k为某个常数,在所有同类数量级的此类排序方法中,快速排序的常数因子k最小。

空间复杂度,最坏的情况下O(n),就是每个数字都作为一次基准,平均情况是O(nlog2n)

时间复杂度,在很大程度上取决于划分算法与序列本身的情况,平均的时间复杂度为O(nlog2n)。

在未改进的情况下,若初始记录序列按照关键字有序或基本有序时,快速排序会退化为冒泡排序,时间复杂度为O(n2)。

快速排序代码实现


史上最易理解的快速排序原理详解以及Arrays.sort方法

运行结果截图

史上最易理解的快速排序原理详解以及Arrays.sort方法

快速排序改进


通常使用“三者取中”的法则来选取枢轴记录,即比较a[start]、a[end]、a[(start+end)/2],取三者取中值记录为枢轴,采用这种方法能够大大改善快去排序在最坏情况下的性能。

Arrays.sort()方法源码

史上最易理解的快速排序原理详解以及Arrays.sort方法


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《史上最易理解的快速排序原理详解以及Arrays.sort方法》的版权归原作者「青城博雅教育科技」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注青城博雅教育科技微信公众号

青城博雅教育科技微信公众号:QCBY_edu

青城博雅教育科技

手机扫描上方二维码即可关注青城博雅教育科技微信公众号

青城博雅教育科技最新文章

精品公众号随机推荐