数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

14 | 排序优化:如何实现一个通用的、高性能的排序函数?

王争 2018-10-22
几乎所有的编程语言都会提供排序函数,比如 C 语言中 qsort(),C++ STL 中的 sort()、stable_sort(),还有 Java 语言中的 Collections.sort()。在平时的开发中,我们也都是直接使用这些现成的函数来实现业务逻辑中的排序功能。那你知道这些排序函数是如何实现的吗?底层都利用了哪种排序算法呢?
基于这些问题,今天我们就来看排序这部分的最后一块内容:如何实现一个通用的、高性能的排序函数?

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

如果要实现一个通用的、高效率的排序函数,我们应该选择哪种排序算法?我们先回顾一下前面讲过的几种排序算法。
我们前面讲过,线性排序算法的时间复杂度比较低,适用场景比较特殊。所以如果要写一个通用的排序函数,不能选择线性排序算法。
如果对小规模数据进行排序,可以选择时间复杂度是 O(n2) 的算法;如果对大规模数据进行排序,时间复杂度是 O(nlogn) 的算法更加高效。所以,为了兼顾任意规模数据的排序,一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
时间复杂度是 O(nlogn) 的排序算法不止一个,我们已经讲过的有归并排序、快速排序,后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用,比如 Java 语言采用堆排序实现排序函数,C 语言使用快速排序实现排序函数。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(88)

  • 刘強
    我们的教育让我们对标准答案的依赖太深了,让我们失去了独立思考的能力。深深的感受到了这一点。思考的过程比标准答案更重要,这句话才是关键。
    2018-10-22
    2
    280
  • Liam
    查看了下Arrays.sort的源码,主要采用TimSort算法, 大致思路是这样的:

    1 元素个数 < 32, 采用二分查找插入排序(Binary Sort)
    2 元素个数 >= 32, 采用归并排序,归并的核心是分区(Run)
    3 找连续升或降的序列作为分区,分区最终被调整为升序后压入栈
    4 如果分区长度太小,通过二分插入排序扩充分区长度到分区最小阙值
    5 每次压入栈,都要检查栈内已存在的分区是否满足合并条件,满足则进行合并
    6 最终栈内的分区被全部合并,得到一个排序好的数组

    Timsort的合并算法非常巧妙:

    1 找出左分区最后一个元素(最大)及在右分区的位置
    2 找出右分区第一个元素(最小)及在左分区的位置
    3 仅对这两个位置之间的元素进行合并,之外的元素本身就是有序的
    2018-10-22
    173
  • 杨伟
    思考过程比答案重要这句话是不假,但是有答案来验证自己的思考是否准确在初学时期也很重要。

    学习知识每个人的理解会不同,有的人可能这么理解有的人可能那样理解。如果没有一个标杆,有些同学就会按照自己错误的理解继续学习下去。

    有了标准答案,同学就可以对照答案来反思自己的理解是否正确。也能够从别人的答案中看到更好的解答也是一种学习。

    当然自己偷懒不思考,依赖标准答案,那肯定是学不好的
    2018-10-22
    102
  • 小确幸
    数据库里面的Order BY,用的是什么排序呢?
    2018-10-22
    3
    51
  • java1.8中的排序,在元素小于47的时候用插入排序,大于47小于286用双轴快排,大于286用timsort归并排序,并在timesort中记录数据的连续的有序段的的位置,若有序段太多,也就是说数据近乎乱序,则用双轴快排,当然快排的递归调用的过程中,若排序的子数组数据数量小,用插入排序。
    2018-10-22
    45
  • 姜威
    总结:如何实现一个通用的高性能的排序函数?
    一、如何选择合适的排序算法?
    1.排序算法一览表
                     时间复杂度 是稳定排序? 是原地排序?
    冒泡排序 O(n^2) 是 是
    插入排序 O(n^2) 是 是
    选择排序 O(n^2) 否 是
    快速排序 O(nlogn) 否 是
    归并排序 O(nlogn) 是 否
    桶排序 O(n) 是 否
    计数排序 O(n+k),k是数据范围 是 否
    基数排序 O(dn),d是纬度 是 否
    2.为什选择快速排序?
    1)线性排序时间复杂度很低但使用场景特殊,如果要写一个通用排序函数,不能选择线性排序。
    2)为了兼顾任意规模数据的排序,一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。
    3)同为O(nlogn)的快排和归并排序相比,归并排序不是原地排序算法,所以最优的选择是快排。
    二、如何优化快速排序?
    导致快排时间复杂度降为O(n)的原因是分区点选择不合理,最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。如何优化分区点的选择?有2种常用方法,如下:
    1.三数取中法
    ①从区间的首、中、尾分别取一个数,然后比较大小,取中间值作为分区点。
    ②如果要排序的数组比较大,那“三数取中”可能就不够用了,可能要“5数取中”或者“10数取中”。
    2.随机法:每次从要排序的区间中,随机选择一个元素作为分区点。
    3.警惕快排的递归发生堆栈溢出,有2中解决方法,如下:
    ①限制递归深度,一旦递归超过了设置的阈值就停止递归。
    ②在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈过程,这样就没有系统栈大小的限制。
    三、通用排序函数实现技巧
    1.数据量不大时,可以采取用时间换空间的思路
    2.数据量大时,优化快排分区点的选择
    3.防止堆栈溢出,可以选择在堆上手动模拟调用栈解决
    4.在排序区间中,当元素个数小于某个常数是,可以考虑使用O(n^2)级别的插入排序
    5.用哨兵简化代码,每次排序都减少一次判断,尽可能把性能优化到极致
    四、思考
    1.Java中的排序函数都是用什么排序算法实现的?有有哪些技巧?
    2018-10-22
    4
    26
  • 李靖峰
    golang标准库中的Sort用的是快排+希尔排序+插排,数据量大于12时用快排,小于等于12时用6作为gap做一次希尔排序,然后走一遍普通的插排(插排对有序度高的序列效率高)。其中快排pivot的选择做了很多工作不是一两句话可以描述出来,是基于首中尾中值的很复杂的变种
    2018-10-29
    24
  • 蛐鸣
    看了一下,.NET里面的Array排序实现:
    1. 三个以内的,直接比较,交换进行实现
    2.大于3个小于16个的,用的是插入排序进行的实现
    3.对于大于16,并且深度限制是0的,用的是堆排序实现的
    4.对于大于15,并且深度限制不是0的,使用的是快速排序;然后快速排序分区使用的也是三数取中法

    作者回复: 👍

    2018-11-02
    21
  • Andrew 陈震
    老师,我有一个问题,关于递归太深导致堆栈溢出的问题。对于这个问题,您说一般有两种解决方法,一是设置最深的层数,如果超过层数了,就报错。对于这样的问题,我想排序一个数列,超过了层数,难道就不排了么?我看有留言说,stl中的sort默认是使用快排的,但当递归深度过大时 会转为使用归并排序。但是归并排序也是递归排序啊,如果两种排序都达到了最深层数怎么处理?另外,在排序之前,能否估算出排序是否超过最深层数呢?如果估算不出,那岂不是要先排一遍,发现超过层数,再换用别的。我的想法是设个阈值,不超过阈值,用一种,超过了,用另一种。

    第二种应对堆栈溢出的方法是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程。这个方法在您的几篇教程里都提到过,但是不详细,您能否稍微详细讲解一下。

    谢谢老师

    作者回复: 太深报错也没问题 不过不建议这么处理
    归并排序比较稳定 栈的深度是logn 非常小 所以不会堆栈溢出
    关于手动模拟栈 你可以看看qsort()函数的实现

    2018-10-22
    1
    19
  • Jerry银银
    说说我觉得文章可能存在的一个问题,再借此问题,正好回答下思考题!
    ----------------------
    文章中有一段话,如下:
    "时间复杂度是 O(nlogn) 的排序算法不止一个,我们已经讲过的有归并排序、快速排序,后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用,比如 Java 语言采用堆排序实现排序函数,C 语言使用快速排序实现排序函数。"
    这里说,”Java语言采用堆排序实现排序函数“,这句话是不是错误的?

    在JDK中,排序相关的主要是两个工具类:Arrays.java 和 Collections.java,具体的排序方法是sort()。这里要注意的是,Collections.java中的sort()方法是将List转为数组,然后调用Arrays.sort()方法进行排序,具体代码如下(留言中代码格式可能有点混乱,讲究看看,也可以自行参看List.sort()):
    default void sort(Comparator<? super E> c) {
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) {
                i.next();
                i.set((E) e);
            }
        }

    在Arrays类中,sort()有一系列的重载方法,罗列几个典型的Arrays.sort()方法如下:
    public static void sort(int[] a) {
         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
     }

    public static void sort(long[] a) {
         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

    public static void sort(Object[] a) {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a);
            else
                ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }
    重载方法虽然多,但是从“被排序的数组所存储的内容”这个维度可以将其分为两类:
    1. 存储的数据类型是基本数据类型
    2. 存储的数据类型是Object
    第一种情况使用的是快排,在数据量很小的时候,使用的插入排序;
    第二种情况使用的是归并排序,在数据量很小的时候,使用的也是插入排序
     
    以上两种场景所用到的排序都是「混合式的排序」,也都是为了追求极致的性能而设计的。另外,第二种排序有个专业的名称,叫:TimSort(可以自行Wikipedia)

    作者回复: 👍 细心,新版本的jdk估计有优化吧,可以从代码中发现:
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a);

    legacy的实现确实是堆排序!

    2019-03-02
    1
    18
  • leo
    排序的思维导图链接:https://share.weiyun.com/5X17MG3
    2018-10-29
    10
  • 等风来
    使用快排如何解决不稳定排序的问题?

    作者回复: 并没解决 所以qsort不稳定

    2018-10-22
    9
  • Random.nextName()
    Google v8中对QuickSort的实现是:
    数据规模在10以内的话使用快排;
    数据规模在10到1000之间时选择中点作为pivot进行快排;
    数据规模在1000以上时,每隔200到215个数选一个数,将选出来的数排序,选择中间值作为pivot进行快排;
    而且还有几个细节:
    1是折半的时候用的是位运算;
    2是每一次遍历都会分成小于pivot,等于pivot,大于pivot的三个区间;
    3是小于pivot和大于pivot这两个区间中数据规模比较小的会递归执行QuickSort,数据规模大的会先通过while循环减小数据规模。
    附上源码链接: https://github.com/v8/v8/blob/master/src/js/array.js
    2018-10-30
    8
  • 学习爱好者
    王老师,总结8种排序算法的那个图,桶排序不一定是稳定排序吧?比如桶内排序用快排的时候

    作者回复: 嗯嗯 用归并或者插入排序就稳定了

    2018-11-05
    7
  • Liam
    关于快排递归过深的处理的疑惑,以及关于 STL 里的 std::sort 是怎么实现的,可以看我这篇博客:https://liam.page/2018/09/18/std-sort-in-STL/
    2018-10-22
    7
  • qsort中为避免递归调用过深,所以在堆上模拟了栈。不知道是否是将递归调用,改写为循环非递归方式呢?

    作者回复: 是的

    2018-10-22
    7
  • AF
    老师,你之前讲的快排、归并,原理我都理解的很清晰,但是一旦到转换成代码的时候,感觉一脸懵逼,你最开始这是这样吗?

    作者回复: 是有点 毕竟代码是写给机器执行的 多看几遍 再自己默写默写

    2018-10-23
    6
  • 落叶飞逝的恋
    老师,你好,我终于认真消化完了前面的知识,没有半点马虎,也给自己打个卡记录。
    关于思考题:
    查看了Java的Arrays.sort
    1.若数组元素个数总数小于47,使用插入排序
    2.若数据元素个数总数在47~286之间,使用快速排序。应该是使用的优化版本的三值取中的优化版本。
    3.若大于286的个数,使用归并排序。
    底层实现的代码比之前示范写的代码校验多,所以目前只能看到这,下面继续加油吧!

    作者回复: 👍

    2018-12-04
    1
    5
  • favorlm
    虽然说思考很重要,但是面试还是需要你实现一种算法。

    作者回复: 留言区点赞最高的就是答案

    2018-11-04
    5
  • 24隋心所欲
    针对 Java 语言:

    1. 对于基本类型的数组,Java 采用的是双枢轴快速排序(Dual-Pivot Quicksort),这个算法是 Java 7 引入的。在此之前,Java 采用的是普通的快速排序,双枢轴快速排序是对普通快速排序的优化,新算法的实现代码位于类 java.util.DualPivotQuicksort 中。

    2. 对于对象类型,Java 采用的算法是 TimSort,TimSort 算法也是 Java 7 引入的。在此之前,Java 采用的是归并排序。TimSort 算法实际上是对归并排序的一系列优化,TimSort 的实现代码位于类 java.util.TimSort 中。

    3. 在这些排序算法中,如果数组长度比较小,它们还会采用效率更高的插入排序。
    2019-03-23
    4
收起评论
88
返回
顶部