极客时间-数据结构与算法

前言

本篇主要记录王争老师在极客时间算法课程中主要提到的核心要点。

课程纪实

复杂度分析方法

用课程中提到的一句话:复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半。

如何分析与统计算法的执行效率和资源消耗

为什么需要复杂度分析?
  • 测试结果非常依赖测试环境:不同的硬件环境,测试的结果自然不同
  • 测试结果受数据规模的影响很大

因此需要一种不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法。

大O复杂度表示法

公式可以表示为:
表达公式
大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

时间复杂度分析
  • 只关注循环执行次数最多的一段代码
    我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了
    示例代码

  • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    总的时间复杂度就等于量级最大的那段代码的时间复杂度

  • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    落实到具体的代码上,我们可以把乘法法则看成是嵌套循环

几种常见时间复杂度实例分析

常见的复杂度量级图解:
复杂度量级

  • 多项式量级
    • O(1)
    • O(logn)、O(nlogn)
    • O(m+n)、O(m*n)
  • 非多项式量级

几种时间复杂度增长关系
复杂度增长关系

空间复杂度分析

时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

浅析最好、最坏、平均、均摊时间复杂度

最好情况

最好情况时间复杂度就是:在 最理想 的情况下,执行这段代码的时间复杂度

最快情况

最坏情况时间复杂度就是:在 最糟糕 的情况下,执行这段代码的时间复杂度

平均情况

这是一个简单的概率论中的知识
平均时间复杂度分析

均摊时间

常见几种基本数据结构

数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某个数据结构或者算法,而是要学习它背后的思想和处理技巧,这些东西才是最有价值的。
如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算法和数据结构的影子。

数组

解释:数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

线性表(Linear List)

线性表逻辑结构

非线性表

之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。
连续的内存空间和相同类型的数据
非线性表逻辑结构

常常会问数组和链表的区别
“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为O(1)”。
正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

数组特点

低效的“插入”和“删除”

插入

如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+ …n)/n=O(n)。

删除

如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。

几点经验
  • ava ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。
  • 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。
  • 还有一个是我个人的喜好,当要表示多维数组时,用数组往往会更加直观。比如Object[][] array;而用容器的话则需要这样定义:ArrayList array。
开篇答疑

为什么大多数编程语言中,数组要从 0 开始编号,而不是从1 开始呢?
正常的寻址公式这样的:
正常的数组寻址公式
如果数组从1开始计数,那么寻址公式就是下面这样的
数组起始为1的时候寻址公式
此时很明显,计算机计算的步骤要比从0开始多计算,因而需要消耗更多的计算资源

链表

先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。
数组需要一块连续的内存空间,而链表恰恰相反

链表分类

单链表、双向链表和循环链表

单链表

单链表模拟结构
注意:第一个结点叫作头结点、最后一个结点叫作尾结点。

循环链表和双向链表

单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点
循环链表模拟结构

双向链表,顾名思义,它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。
双向链表模拟结构
根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

双向循环链表
双向循环链表模拟结构

用空间换时间

当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构
如果内存比较紧缺,比如代码跑在手机或者单片机上,这个时候,就要反过来用时间换空间的设计思路。
数组与链表操作时间复杂度

开篇答疑(一)

如何基于链表实现 LRU 缓存淘汰算法?

    1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
    1. 如果此数据没有在缓存链表中,又可以分为两种情况
    • 如果此时缓存未满,则将此结点直接插入到链表的头部;
    • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
      当然也可以用数组来完成这个判断过程
如何轻松写出正确的链表代码?
技巧一:理解指针或引用的含义

没啥好说的,如果是通过C/C++来实现,需要注意

技巧二:警惕指针丢失和内存泄漏

一个典型错误示例:
错误的插入节点步骤
正确的示例片段:

1
2
p->next = x; // 将p的next指针指向x结点
x->next = p->next; // 将x的结点的next指针指向b结点

删除链表结点时,也一定要记得手动释放内存空间

技巧三:利用哨兵简化实现难度

在任何时候,不管链表是不是空,head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反,没有哨兵结点的链表就叫作不带头链表。
带头链表模拟结构
这种利用哨兵简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划

技巧四:重点留意边界条件处理
  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?
技巧五:举例画图,辅助思考

画图思考示例

技巧六:多写多练,没有捷径

几个核心要点:

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第n个节点
  • 求链表的中间节点

栈是一种“操作受限”的线性表,只允许在一端插入和删除数据
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

如何实现一个栈?
顺序栈

用数组实现的栈,我们叫作顺序栈,支持动态扩容的顺序栈
来看下面的思考:
一些假设和定义
入栈的时间复杂度

链式栈

顾名思义,用链表来实现的

栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。

栈在表达式求值中的应用
栈在括号匹配中的应用

队列

如何理解“队列”?

入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。
入栈的时间复杂度

循环队列
阻塞队列和并发队列
阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作
在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
阻塞队列模拟结构

并发队列

最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列

开篇答疑

线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?各种处理策略又是如何实现的呢?

  • 是非阻塞的处理方式,直接拒绝任务请求;
  • 阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续处理
  • 基于链表
    基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。
  • 基于数组
    而基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。

基础排序

各基础排序时间复杂度比较
基础排序时间复杂度比较

如何分析一个“排序算法”?

排序算法的执行效率
  • 最好情况、最坏情况、平均情况时间复杂度
  • 分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。
  • 为什么要区分这三种时间复杂度呢?第一,有些排序算法会区分,为了好对比,所以我们最好都做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。
时间复杂度的系数、常数 、低阶

对同一阶时间复杂度的排序算法性能对比的时候, 我们就要把系数、常数、低阶也考虑进来。

比较次数和交换(或移动)次数

基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in place)。
原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。我们今天讲的三种排序算法,都是原地排序算法。

排序算法的稳定性

稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变
基础排序时间复杂度比较

冒泡排序(Bubble Sort)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。
冒泡排序示例步骤拆解

几点关于冒泡排序的思考
  • 冒泡排序是原地排序算法吗?
    冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是一个原地排序算法。
  • 冒泡排序是稳定的排序算法吗?
    在冒泡排序中,只有交换才可以改变两个元素的前后顺序。
    保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
  • 冒泡排序的时间复杂度是多少?
    最好情况时间复杂度是 O(n)
    最坏情况时间复杂度为 O(n)。
    用概率论方法定量分析平均时间复杂度,涉及的数学推理和计算就会很复杂。
    一种思路,通过“有序度”和“逆序度”这两个概念来进行分析。
    有关有序度与无序度的讨论
    有序度是数组中具有有序关系的元素对的个数
    例如:
    数组的有序度
    对于一个倒序排列的数组,比如 6,5,4,3,2,1,有序度是 0;对于一个完全有序的数组,比如 1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。

一个公式:逆序度 = 满有序度 - 有序度。

拿前面举的那个冒泡排序的例子:
一则冒泡排序示例分析
逆序度,也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12,要进行 12 次交换操作。
对于包含 n 个数据的数组进行冒泡排序,平均交换次数是多少呢?最坏情况下,初始状态的有序度是 0,所以要进行 n*(n-1)/2 次交换。最好情况下,初始状态的有序度是 n*(n- 1)/2,就不需要进行交换。我们可以取个中间值 n*(n-1)/4,来表示初始有序度既不是很高也不是很低的平均情况。
平均情况下,需要 n*(n-1)/4 次交换操作,比较操作肯定要比交换操作多,而复杂度的上限是 O(n ),所以平均情况下的时间复杂度就是 O(n )。

插入排序(Insertion Sort)

一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?
保持有序的插入排序示例

步骤拆解

我们将数组中的数据分为两个区间,已排序区间和未排序区间。
初始已排序区间只有一个元素,就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程, 直到未排序区间中元素为空,算法结束。
插入排序分步骤拆解

几点思考
  • 插入排序是原地排序算法吗?
    实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。
  • 插入排序是稳定的排序算法吗?
    保持原有的前后顺序不变,所以插入排序是稳定的排序算法
  • 插入排序的时间复杂度是多少?
    每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为 O(n )

选择排序(Selection Sort)

也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
选择排序原理示意图
选择排序空间复杂度为 O(1),是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n )
选择排序是一种不稳定的排序算法。

开篇答疑

冒泡排序和插入排序的时间复杂度都是O(n ),都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢?

  • 冒泡排序不管怎么优化,元素交换的次数是一个固定值,是原始数据的逆序度。
  • 插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。
  • 冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。
  • 插入排序的优化感兴趣,可以自行学习一下希尔排序
总结

对于小规模数据的排序,用起来非常高效。但是在大规模数据排序的时候,这个时间复杂度还是稍微有点高,所以我们更倾向于用下一节要讲的时间复杂度为 O(nlogn) 的排序算法。

如何用快排思想在O(n)内查找第K大元素?

两种时间复杂度为 O(nlogn) 的排序算法,归并排序和快速排序。这两种排序算法适合大规模的数据排序
我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot,对数组 A[0…n-1] 原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。
如果 p+1=K,那 A[p] 就是要求解的元素;如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间,我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理,如果K < p+1,那我们就在 A[0…p-1] 区间查找。

归并排序

核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
归并排序分解图
分治是一种解决问题的处理思想,递归是一种编程技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 归并排序算法, A 是数组,n 表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取 p 到 r 之间的中间位置 q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
归并排序的性能分析
  • 归并排序是稳定的排序算法吗?
    归并排序稳不稳定关键要看merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码
  • 归并排序的时间复杂度是多少?
    不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。
    如果我们定义求解问题 a 的时间是 T(a),求解问题 b、c 的时间分别是 T(b) 和 T( c),那我
    们就可以得到这样的递推关系式:
    T(a) = T(b) + T(c) + K
    不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。
  • 第三,归并排序的空间复杂度是多少?
    归并排序的时间复杂度任何情况下都是 O(nlogn)
    有一个致命的“弱点”,那就是归并排序不是原地排序算法。

快速排序

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。
我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。
快速排序分区示意图

根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。
递推公式:
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件:
p >= r
用代码表示就如下所示:

1
2
3
4
5
6
7
8
9
10
11
// 快速排序,A 是数组,n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
快速排序之原地分区函数

伪代码如下:
快速排序原地分区函数伪代码示例

原地分区后的快速排序步骤拆解示例
因为分区的过程涉及交换操作,如果数组中有两个相同的元素,比如序列 6,8,7,6,3,5,9,4,在经过第一次分区操作之后,两个 6 的相对先后顺序就会改变。所以,快速排序并不是一个稳定的排序算法

快排与归并的不同

快排和归并用的都是分治思想,递推公式和递归代码也非常相似,那它们的区别在哪里呢?
图解快排与归并的不同
可以发现,归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法,但是它是非原地排序算法。我们前面讲过,归并之所以是非原地排序算法,主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数,可以实现原地排序,解决了归并排序占用太多内存的问题。

线性排序

三种时间复杂度是O(n)的排序算法:桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的,所以我们把这类排序算法叫作线性排序( Linear sort

桶排序

桶排序示例
桶排序看起来很优秀,那它是不是可以替代我们之前讲的排序算法呢?
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加載到内存中。
例如:
比如说我们有10GB的订单数据,我们希望按订单金额(假设金额都是正整数)进行排序,但是我们的内存有限,只有几百MB,没办法一次性把106B的数据都加载到内存中。这个时候该怎么办呢?
先扫描一遍文件,看订单金额所处的数据范围。假设经过扫描之后我们得到,订单金额最小是1元最大是10万元。我们将所有订单根据金额划分到100个桶里,第一个桶我们存储金额在1元到1000元之内的订单,第二桶存储金额在1001元到2000元之内的订单,以此类推。每一个桶对应一个文件,并且按照金额范围的大小顺序编号命名(00,01,0299)
如果订单金额在1到10万之间均匀分布,那订单会被均匀划分到100个文件中,每个小文件中存储大约100MB的订单数据,我们就可以将这100个小文件依次放到内存中,用快排来排序
但是订单按照金额在1元到10万元之间并不一定是均匀分布的:
如何借助桶排序的处理思想来解决这个问题。
可以先扫描一遍文件,看订单金额所处的数据范国。假设经过扫描之后我们得到; 最小是1元,最大是10万元。我们将所有订单根据金额划分到100个桶里,第门存储金额在1元到1000元之内的订单,第二桶存储金额在1001元到2000元单,以此类推。每一个桶对应一个文件,并且按照金额范围的大小顺序编号命名01,02.99)。
针对这些划分之后还是比较大的文件,我们可以继续划分,比如,订单金额在1元到1000 元之间的比较多,我们就将这个区间继续划分为10个小区间,1元到100元,101元到200元,201元到300元.901元到1000元。如果划分之后,101元到200元之间的订单还是太多,无法一次性读入内存,那就继续再划分,直到所有的文件都能读入内存为止

计数排序( Counting sort)

计数排序其实是桶排序的一种特殊情况
举例:考生的满分是900分,最小是0分,这个数据的范围很小,所以我们可以分成901个桶对应分数从0分到900分。根据考生的成绩,我们将这50万考生划分到这901个桶里。

深入理解计数含义

计数排序的算法思想就是这么简单,跟桶排序非常类似,只是桶的大小粒度不一样。不过, 为什么这个排序算法叫“计数”排序呢?“计数”的含义来自哪里呢?
【举例】假设只有8个考生,分数在0到5分之间。这8 个考生的成绩我们放在一个数组A[8]中,它们分別是:2,5,3,0,2,3,0,3。
考生的成绩从0到5分,我们使用大小为6的数组C[6]表示桶,其中下标对应分数。如下图所示:
考生成绩划分后的计数数组
从上图中可以看出:
思考
成绩3的划分场景

关键问题:如何计算位置?

如何快速计算出,每个分数的考生在有序数组中对应的存储位置呢?
我们对C[6]数组顺序求和,C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数k的考生个数,如下图所示:
顺序求和之后的数组
我们从后到前依次扫描数组 A。比如,当扫描到 3 时,我们可以从数组 C 中取出下标为 3的值 7,也就是说,到目前为止,包括自己在内,分数小于等于 3 的考生有 7 个,也就是说 3 是数组 R 中的第 7 个元素(也就是数组 R 中下标为 6 的位置)。当 3 放入到数组 R中后,小于等于 3 的元素就只剩下了 6 个了,所以相应的 C[3] 要减 1,变成 6。
以此类推,当我们扫描到第 2 个分数为 3 的考生的时候,就会把它放入数组 R 中的第 6 个元素的位置(也就是下标为 5 的位置)。当我们扫描完整个数组 A 后,数组 R 内的数据就是按照分数从小到大有序排列的了。
拆解计算步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 计数排序,a 是数组,n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组 c,下标大小 [0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数,放入 c 中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组 r,存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤,有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝给 a 数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
总结

计数排序只能用在数据范围不大的场景中,如果数据范围 k 比要排序的数据n 大很多,就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

比如,还是拿考生这个例子。如果考生成绩精确到小数后一位,我们就需要将所有的分数都先乘以 10,转化成整数,然后再放到 9010 个桶内。再比如,如果要排序的数据中有负数,数据的范围是 [-1000, 1000],那我们就需要先对每个数据都加 1000,转化成非负整数。

基数排序( Radix sort)

假设我们有10万个手机号码,希望将这10万个手机号码从小到大排序,你有什么比较快速的排序方法呢?
图解计数排序过程
这里按照每位来排序的排序算法要是稳定的,否则这个实现思路就是不正确的。因为如如果是非稳定排序算法,那最后一次排序只会考虑最高位的大小顺序,完全不管其他位的大小关系,那么低位的排序就完全没有意义了。
有时候要排序的数据并不都是等长的
实际上,我们可以把所有的单词补齐到相同长度,位数不够的可以在后面补“0”,因为根据ASCI值,所有字母都大于“0”,所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了

基数排序对要排序的数据是有要求的,需要可以分割出独立的“位”来比较,而且位之间有递进的关系,如果a数据的高位比b数据大,那剩下的低位就不用比较了。除此之外,每一位的数据范围不能太大,要可以用线性排序算法来排序,否则,基数排序的时间复杂度就无法做到O(n)了。

排序优化

如何实现一个通用的、高性能的排序函数?
各排序函数时间复杂度一览
为了兼顾任意规模数据的排序, 一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
快速排序在最坏情况下的时间复杂度是 O(n ),如何来解决这个“复杂度恶化”的问题呢?

如何优化快速排序?

每次分区点都选择最后一个数据,那快速排序算法就会变得非常糟糕,时间复杂度就会退化为 O(n )。实际上,这种 O(n ) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。
最理想的分区点是:被分区点分开的两个分区中,数据的数量差不多。

  • 三数取中法
    我们从区间的首、尾、中间,分别取出一个数,然后对比大小,取这 3 个数的中间值作为分区点。
  • 随机法
    随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。

递归要警惕堆栈溢出。为了避免快速排序里,递归过深而堆栈过小,导致堆栈溢出,我们有两种解决办法:第一种是限制递归深度。一旦递归过深,超过了我们事先设定的阈值,就停止递归。第二种是通过在堆上模拟实现一个函数调用栈,手动模拟递归压栈、出栈的过程,这样就没有了系统栈大小的限制。

举例分析排序函数

Glibc 中的 qsort() 函数举例

  • qsort() 会优先使用归并排序来排序输入数据
  • 要排序的数据量比较大的时候,qsort() 会改为用快速排序算法来排序。
  • 提到的递归太深会导致堆栈溢出的问题,qsort() 是通过自己实现一个堆上的栈,手动模拟递归来解决的
  • 用到了插入排序。在快速排序的过程中,当要排序的区间中,元素的个数小于等于 4 时,qsort() 就退化为插入排序,不再继续用递归来做快速排序,

实战

实战总结篇,限于本文篇幅可能会过长,该部分参见个人另一篇博客中的具体实战讨论细节
传送门:极客时间-数据结构与算法-实战篇