江苏龙网

  1. 首页 > 生活 > >

从大方向和思路上来说，怎样提升排序算法的效率

【从大方向和思路上来说，怎样提升排序算法的效率】 邀请窝这么一个辣鸡OIer干什么呀！
emm...排序算法....
那就...分析复杂度...分析排序对象性质对排序可行效率的影响（比如整数排序下界不是 从大方向和思路上来说，怎样提升排序算法的效率
什么的...
还有...算法效率是否稳定...如果效率不稳定的话考虑其期望（及方差）什么的...
emm...还有...算法本身在复杂度之外的常数...针对不同输入（比如有序、逆序和随机）的效率对比...
总感觉窝越说越跑题....
妈耶窝到底为什么会被邀请啊！

■网友
TAOCP整个一大卷 应该是第三卷吧，几百页都在写这个问题，我认为已经被充分讨论了，剩下的问题不是不重要就是很困难。也没必要新写报告，做个读书笔记就好
■网友
呵呵呵，不用钓鱼了。你觉得有深刻认识的人会跟你讲吗？那分分钟都代表着进一步的突破。

■网友
基于比较的排序算法最优下界不可能超过O（nlgn），再怎么提升效率也不可能突破这个界限啦...也许可以从优秀的排序算法比如快排，归并上找点灵感...例如我觉得两种算法的共性是处理数组这种线性结构的时候都把它当成了树形结构，merge每次对数组的划分，可以想象成一棵二叉树，而快排每次的pivot，恰好可以组成一棵BST。还有在思想上都用了分治神马的(?˙ー˙?)
■网友
呃，这个问题。。。泻药吧
一些愚见，上班时间忙里偷闲，只说性能
先来考虑一下算法的问题。如果让你给一堆看不见牌面的扑克牌排个序，最笨的方法是什么呢？那就是每次都把所有的牌看一遍，找到最小的（或者最大的，这里举例用升序），拿出来，然后再回去拿剩下的牌里最小的，如此往复，最后可以得到一个有序的序列，就完成了排序。放到算法里，这就是冒泡排序的思想，算法时间复杂度是n2
还是刚刚的问题，如果想快点儿，那么可以怎么做呢？可以这样，先取一个基准元素，然后再把比它小的数字的牌放左面，不比它小的放右面，那么遍历一次以后你得到的就是一个初步有序的序列。接下来要做的就是把已经分成两列的自序列按照刚刚的方式再操作一次，依次循环，等到最小的自序列只有两张牌的时候，分无可分，这时候合并起来，可以得到一个有序的数列，这就是快速排序，是不是快了很多？算法时间复杂度是nlogn级别。类似的还有合并排序，将小的序列合并成大的序列，本质都是利用分治法
当然也不是不能改进。以快速排序为例，实际上快速排序大部分时间都花在了划分自序列上，那么可以从这点入手对算法进行改进。数据规模较小，或许堆排序更适合，但如果数据上了规模，堆排序就并不是那么突出了，所以当序列小到一定规模的时候，用快排就不合适了，可以利用堆排序。算法之间互有优劣，不同情况下算法的优势各不相同，很多时候设计排序算法时，可以集合几个排序算法的优劣，然后在不同情况下使用，达到更优
本质来说，排序还是二分法和分治法的应用。为何排序算法在数据处理中有如此高的地位，实际上是很多时候查询算法（本质还是二分法）的优化空间并不是很大，对于查询而言，当然是有序的序列更快，然而数据处理本质上还是增删改，查询作为最重要的一环，当然要对查询的速度做优化了


    推荐阅读


    上一篇：怎样评价部分果粉的选择性质疑

    下一篇：|新需求带动新增长 连云港节庆消费全面升温