文档章节

sort()

曾劲松
 曾劲松
发布于 2016/04/11 21:39
字数 1159
阅读 60
收藏 0

   STL的sort()算法,数据量大时采用Quick Sort,分段递归排序,一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用Insertion Sort。如果递归层次过深,还会改用Heap Sort。本文先分别介绍这个三个Sort,再整合分析STL sort算法(以上三种算法的综合) -- Introspective Sorting(内省式排序)。

指导博文http://www.cnblogs.com/imAkaka/articles/2407877.html

指导博文2九大排序算法总结

为什么是Insertion Sort,而不是Bubble Sort。

选择排序(Selection sort),插入排序(Insertion Sort),冒泡排序(Bubble Sort)。这三个排序是初学者必须知道的三个基本排序方式,且他们速度都不快 -- O(N^2)。选择排序就不说了,最好情况复杂度也得O(N^2),且还是个不稳定的排序算法,直接淘汰。

可冒泡排序和插入排序相比较呢?

首先,他们都是稳定的排序算法,且最好情况下都是O(N^2)。那么我就来对他们的比较次数和移动元素次数做一次对比(最好情况下),如下:

插入排序:比较次数N-1,移动元素次数2N-1。

冒泡排序:比较次数N-1,无需移动元素。(注:我所说的冒泡排序在最基本的冒泡排序基础上还利用了一下旗帜的方式,即寻访完序列未发生数据交换时则表示排序已完成,无需再进行之后的比较与交换动作)

那么,这样看来冒泡岂不是是更快,我可以把上述的__final_insertion_sort()函数改成一个__final_bubble_sort(),把每个子序列分别进行冒泡排序,岂不是更好?

事实上,具体实现时,我才发现这个想法错了,因为写这么一个__final_bubble_sort(),我没有办法确定每个子序列的大小,可我还是不甘心呐,就把bubble_sort()插在__introsort_loop()最后,这样确实是每个子序列都用bubble_sort()又排序了一次,可是测试结果太惨了,由此可以看书Bubble Sort在“几近排序但尚未完成”的情况下是没多少改进作用的。

为什么不直接用Heap Sort

在算法导论课后西提2-2中又问了”冒泡排序和插入排序哪个更快“呢?

一般的人回答:“差不多吧,因为渐近时间都是O(n^2)”。

但是事实上不是这样的,插入排序的速度直接是逆序对的个数,而冒泡排序中执行“交换“的次数是逆序对的个数,因此冒泡排序执行的时间至少是逆序对的个数,因此插入排序的执行时间至少比冒泡排序快。

堆排序将所有的数据建成一个堆,最大的数据在堆顶,它不需要递归或者多维的暂存数组。算法最优最差都是O(NlogN),不像快排,如果你人品够差还能恶化到O(N^2)。当数据量非常大时(百万数据),因为快排是使用递归设计算法的,还可能发出堆栈溢出错误呢。

那么为什么不直接用Heap Sort?或者说给一个最低元素阈值(__stl_threshold)时也给一个最大元素阈值(100W),即当元素数目超过这个值时,直接用Heap Sort,避免堆栈溢出呢?

对于第一个问题,我测试了一下,发现直接用Heap Sort,有时还没有Quick Sort快呢,查阅《算法导论》发现,原来虽然Quick和Heap的时间复杂性是一样的,但堆排序的常熟因子还是大些的,并且堆排序过程中重组堆其实也不是个省时的事。

VS2010版STL中的sort竟比我自己写的快这么多?

    首先,上文实现的这个Introsort是参照SGI STL写的,于是,我斗胆在VS2010中拿他与std:sort比了比快慢。于是就随机产生两个百万数据的vector用来测试。结果发现,VS中sort的速度竟是我的10倍以上的效率。顿时对微软萌生敬意,可是当我仔细翻看源码时.....
    原来,microsoft的sort并没有比sgi的sort快。只是在排序vector时,microsoft把vector的本质数据“萃取”出来了。
即,取消了vector在++时的边界检查语句,把vector::iterator当指针一般使用。所以才在对vector排序时会比我自己写的introsort算法快那么多呢。




© 著作权归作者所有

下一篇: for_each()
曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问
linux之sort,unip,cut

用sort对文件中的行进行排序,或者根据给定的标准输出排序结果。以下是对sort的部分用法的总结。 sort -d 可以使sort忽略标点符号以及一些其他的特殊字符,然后对文件中的行进行排序。 sort...

大圈
2015/08/11
104
0
shell:wc、sort、uniq

文本排序 sort 文本去重 uniq 先排序再去重 -c: 显示文件中行重复的次数 -d: 只显示重复的行(相邻的行) 文本统计 wc -l:多少行 -w:多少单词 -c:多少字符 -L:最长的一行包含了多少个字符...

许小哥
07/25
5
0
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
从apache日志中找出访问IP

apache日志分析可以获得很多有用的信息,现在来试试最基本的,获取最多访问的前10个IP地址及访问次数。 cat access.log |awk '{print $1}' |sort |uniq -c |sort -rn |wc -l 统计访问IP的总数...

技术小阿哥
2017/11/28
0
0
linux下grep分析apache日志的命令集合

linux下grep分析apache日志的命令集合,不可错过的好文章,有了这些命令,秒杀江湖中大部分的apache日志分析。 实例: 月份英文简写英文全称 一月Jan.January 二月Feb.February 三月Mar.Mar...

hmc0316
2013/03/06
2.8K
0

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
9
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
953
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部