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

发表于 更新于 分类于
本文字数： 9.5k 阅读时长 ≈ 34 分钟

前言

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

课程纪实

复杂度分析方法

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

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

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

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

大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() 就退化为插入排序,不再继续用递归来做快速排序,

实战

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