🍕 快排空间复杂度
首先, 快排在执行 partition 的过程中会申请空间, 该空间用来存储划分后的数据, 每次划分结束后可以确定一个(或一批)数的正确位置。
考虑最坏的情况, 每次划分后, 划分值所在的正确位置都是在两侧。 此时, 每次递归申请的空间是 N, N-1, N-2, ... 故最差情况下空间复杂度是 O(N^2)。
考虑最好的情况, 每次划分后, 划分值所在的正确位置都在中间。 此时, 每次递归申请的空间是是母问题的一半(左侧递归结束后空间会释放, 释放的空间可以供右侧递归使用), 故最好情况下空间复杂度是 O(log(N))。
和计算时间复杂度类似, 随机选取划分值时, 划分的位置是等概率随机的, 通过求概率的累加, 最终能收敛到 log(N) 的水平。
故随机快排的空间复杂度一般认为是 O(log(N))
🍕 完全二叉树
什么是完全二叉树? 看下面几棵树的结构应该就明白了
完全二叉树? ✔️ || 完全二叉树? ❌
* * * | * * *
/ \ / \ / \ | / / \ / \
* * * * * * | * * * * *
/ / \ / / \ / \ | / \ / / \ \
* * * * * * * * | * * * * * *简单的说, 完全二叉树, 就是只允许树的 最后一层 出现 右侧缺口, 否则就不是完全二叉树。
在学习二叉树时, 我们常常画出数的结构图来学习, 比如下面这样:
1
/ \
2 3
/ \ /
4 5 6但在计算机上, 二叉树一般使用数组来存储。
举例, 一个完全二叉树 [4,5,1,2,4,5], 它所对应的树结构如下所示,。
每个节点上显示的是元素值:
4
/ \
5 1
/ \ /
2 4 5每个节点上显示的是下标
0
/ \
1 2
/ \ /
3 4 5对于完全二叉树, 有以下规律: 设 i 为节点下标, heap_size 为节点数量
- 它的左侧子节点下标为
2*i+1 - 它的右侧子节点下标为
2*i+2 - 它的父节点下标为
(i-1)/2 - 若
i < heap_size, 则说明 i 没有越界。
利用这些规律, 对任一节点, 我们可以根据其下标很容易的找到它的父节点, 左右两个子节点的位置。 这样一来, 我们就可以在数组这一结构上, 实现对完全二叉树树的相关操作了, 比如交换某一节点和其父节点: swap(tree, i, (i-1)/2)
🍕 堆
堆是一种特殊的完全二叉树, 堆分为大根堆和小根堆
- 大根堆: 每个节点的值都 大于等于 其子节点, 一棵(子)树中最 大 值是头节点
- 小根堆: 每个节点的值都 小于等于 其子节点, 一棵(子)树中最 小 值是头节点
小根堆和大根堆本质上是一样的, 下面以大根堆为例。
维持大根堆 - heapInsert, heapify
有一个大小为 heap_size 的堆:
添加一个数到堆中时, 维持大根堆的方法如下:
- 将新元素添加到堆的末尾, 作为一个节点存在。
- 比较该节点与父节点, 若该节点 > 父节点, 则交换这两个节点。
- 重复步骤 2, 直到该节点 >= 父节点, 或者没有父节点 这个过程叫做 heap insert
删除大根堆中的最大值时, 维持大根堆方法如下:
- 用最后一个元素覆盖根节点, 即
arr[0] = arr[heap_size-1] - 剔除了一个元素后, 记得更新 heap_size, 即
heap_size--
- 此时完成了删除最大值操作, 接下来要维持大根堆
- 从根节点开始, 将它与左右两个子节点的最大值比较。 (因为刚刚是将最后一个元素放到根节点上了, 所以是从根节点开始)
- 若根节点 < 最大值, 则将根节点与最大值所对应的子节点交换
- 继续与最大的子节点比较, 然后交换。 以此类推, 直到没有子节点, 或者比最大的子节点大。 这个过程叫做 heapify (heapify 表示 "堆化", 具体看后面的将完全二叉树转换为大根堆就懂了)
综上, 可总结:
- 修改堆的最后一个节点时, 需执行 heap insert 来维持大根堆;
- 修改根节点时, 需执行 heapify 来维持大根堆。
- 而当修改中间某个节点时, 维持大根堆的方法如下:
- 比较前后两个值
- 如果值变大了, 说明该值有"上浮"的趋势, 故执行 heap insert
- 如果值变小了, 说明该值有"下沉"的趋势, 故执行 heapify
heap insert 🌰
假设当前有这么一个堆, 它的结构和所对应的数组如下所示:
arr: [6, 3, 5]
heap: 6
/ \
3 5先新增一个数 7, 执行 heap insert 过程如下:
将新元素添加到堆的末尾, 作为一个节点存在
arr: [6, 3, 5, ⑦]
heap: 6
/ \
3 5
/
⑦
比较该节点和父节点, ⑦ > 3, 故交换两个节点
arr: [6, ⑦, 5, 3]
heap: 6
/ \
⑦ 5
/
3
继续比较, ⑦ > 6, 故交换两个节点
arr: [⑦, 6, 5, 3]
heap: ⑦
/ \
6 5
/
3
此时没有父节点了, 故结束 heap insert 过程老师代码如下:
java
// 某个数当前位于 index 位置, arr 是堆的数组结构
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index-1)/2]) {
swap(arr, index, (index-1)/2);
index = (index-1) / 2;
}
}heapify 🌰
假设有一个 heap_size=8 的堆, :
arr: [9, 7, 8, 6, 5, 3, 2, 1]
heap: 9
/ \
7 8
/ \ / \
6 5 3 2
/
1先删除最大值:
arr: [1, 7, 8, 6, 5, 3, 2], 1
heap_size = 7
heap: 1
/ \
7 8
/ \ / \
6 5 3 2
----/---- 断掉
1然后从根节点开始, 执行 heapify 过程:
arr: [①, 7, 8, 6, 5, 3, 2]
heap: ①
/ \
7 8
/ \ / \
6 5 3 2
取出最大子节点8, 比较发现 ① < 8, 故交换
arr: [8, 7, ①, 6, 5, 3, 2]
heap: 8
/ \
7 ①
/ \ / \
6 5 3 2
取出最大子节点 3, 比较发现 ① < 3, 故交换
arr: [8, 7, 3, 6, 5, ①, 2]
heap: 8
/ \
7 3
/ \ / \
6 5 ① 2
没有子节点了, END.老师代码如下:
java
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1
while (left < heapSize) {
// 获取最大的子节点
int largest = (left+1 < heapSize) && (arr[left+1] > arr[left])
? left + 1 : left;
// 比较当前节点和最大的子节点, 看看最大的是哪个值
largest = arr[largest] > arr[index] ? largest : index;
// 如果大于最大的子节点, 则直接退出
if (largest == index) {
break;
}
// 小于最大的子节点, 则交换两个节点, 然后继续循环
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}维持大根堆的代价(复杂度)
对于堆(完全二叉树), 有 n 个节点, 它的高度是 logN 级别。
维持大根堆, 核心就是两个操作: heap insert 和 heapify。
对于这两个操作, 易得他们探索的深度不会大于树的高度。 所以维持大根堆的代价是 logN 级别的。 (同理, 维持小根堆的代价也是一样的)
堆存储中位数
一个数据流中, 随时可以取得中位数。 即用户不断地给你一个数字, 你要能够从已给的数组中返回一个中位数, 并且添加数字和返回中位数的时间复杂度够低。
【思路】:
- 中位数, 即一段数组排序后中间的数字, 如果是偶数个, 则中间两个数相加除 2
- 也就是说, ……xMy……, M 是中位数, 假设是数组是升序的, 则我们可以确定 x 在左边肯定是最大值, y 在右边肯定是最小值。
- 所以我们可以利用大根堆加小根堆来实现需求, 大根堆始终存储中位数左边的内容, 小根堆存储中位数右边的内容
【步骤】:
- 维持一个大根堆一个小根堆
- 用户给的第一个数字, 直接进大根堆
- 再给一个数字
- 如果 数字 ≤ 大根堆堆顶, 将该数字加入大根堆
- 否则将该数字加入小根堆
- 将数字添加到堆后, 比较两个堆的元素数量,
- 如果差值 ≥ 2, 则将元素多的那个堆的堆顶元素, 添加到元素少的堆中。
- 比如 大根堆 size 比小根堆 size 大, 则将大根堆的堆顶元素加入到小根堆中
- 反之, 将小根堆的堆顶元素加入到大根堆中。
🍕 堆排序
大根堆的根节点始终是最大值。 换句话说, "维持大根堆" 能够获取到最大值。
堆排序, 就是不断执行 "维持大根堆", 每次都取出最大值, 周而复始, 最终就可以成功排好序。 而 "维持大根堆" 最重要的两个步骤是 heap insert 和 heapify, 故堆排序也是紧紧围绕这两个步骤展开的。
堆排序步骤如下:
- 初始数组 arr, 大小为 heap_size
- 先将数组转换为大根堆。
- 将根节点与最后一个节点交换, 然后 “剔除” 最后的节点
- 执行 heapipy 操作, 此时数组又是大根堆 (因为是根节点变了, 所以执行的是 heapify 操作)
- 重复步骤 3 和 4, 直到节点剔除完成(heap_size=0), 此时的 arr 就是有序的了
说明: 步骤 2 有两种处理方式
- 将待排序数组的元素通过 heap insert 的方式加入堆(arr)中, 完成数组转换为大根堆这一需求。
- 直接将待排序数组看成是一个完全二叉树, 然后将完全二叉树转换为大根堆。 这种方式执行速度比第一种方式快, 步骤如下:
- 从最后一个节点开始, 执行 heapify 操作。 (也可以从倒数第二层的最右侧节点开始执行 heapify 操作)
- 从后往前, 继续为每个节点执行 heapify 操作, 直到所有节点都完成 heapify 操作
老师代码
java
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 将待排序数组 arr 的元素是一个一个加进堆中
for (int i = 0; i < arr.length; i++) { // O(N)
// 通过 heap insert 就能够保证最终数组是大根堆
heapInsert(arr, i); // O(logN)
}
// 将数组转换为大根堆
int heapSize = arr.length
// 每次将最大值与最后节点交换, 然后堆减去最后一个节点, 执行 heapify 维持大根堆
swap(arr, 0, --heapSize);
while (heapSize > 0) { // O(N)
heapify(arr, 0, heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index-1)/2]) {
swap(arr, index, (index-1)/2);
index = (index-1) / 2;
}
}
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int largest = (left + 1 < heapSize) && (arr[left+1] > arr[left])
? left+1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}通过代码可以看出, 堆排序的时间复杂度是 O(N*log(N)), 空间复杂度是 O(1) (因为只是用了有限的几个变量, 并且没有递归, 所以空间复杂度是 O(1))。 相比其他时间复杂度为 O(N*log(N)) 的排序算法, 堆排序的空间复杂度是最低的, 相对的归并排序空间复杂度是 O(n), 随机快速排序(在长期数学期望上)空间复杂度是 O(logN)。
将完全二叉树转换为大根堆
伪代码
js
function 完全二叉树转换为大根堆:
for ( 从最后一个节点开始向前遍历, 直到遍历完二叉树所有节点) {
对当前节点执行 heapify() 操作
}
function heapify:
while ( 当前节点有子节点 ) {
获取最大子节点 largest
if 当前节点 < 最大子节点
交换(当前节点, 最大子节点)
else
break
}这种方式的时间复杂度是 O(N), 分析如下:
设共有 N 个节点
最后一层 N/2 个节点, 他们执行 heapify 时, 因为他们没有子节点, 所以执行 heapify 时不向下移动, 姑且这将算作 1 个操作
倒数第二层 N/4 个节点, 他们执行 heapify 时, 只往下移动 1 层, 算作 2 个操作
倒数第三层 N/8 个节点, 往下移动 2 层, 3 个操作
...根据上面步骤, 可以得出执行时间 O(N)
堆排序适合的情况
堆排序非常适合解决几乎有序的数据。 比如下面的题目:
题目: 已知一个几乎有序的数组, 几乎有序是指, 如果把数组排好顺序的话, 每个元素移动的距离可以不超过 k, 并且 k 相对于数组来说比较小。 请选择一个合适的排序算法针对这个数据进行排序。
基本思路: 利用小根堆, 定义一个大小为 k 的小根堆, 每算出一个最小值后, 就将最小值弹出。 最终将所有最小值输出, 就可以得到排序好的数据。
为什么是小根堆呢? 因为题目潜在的含义是该数组整体的趋势一定是升序的, 依据是题目中的"移动距离不超过 k, k 的值小于数组长度"。
举个🌰：
假设 k = 6, 数组具体是什么值不重要, 这不是我们分析的重点。
定义一个小根堆, 这个小根堆的节点数为 7
┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐
│ ││ ││ ││ ││ ││ ││ │
└ ─0─ ┘└ ─1─ ┘└ ─2─ ┘└ ─3─ ┘└ ─4─ ┘└ ─5─ ┘└ ─6─ ┘
位置 0, 移动 6 个距离后就是位置 6为什么是 7 呢? 题意说了, 每个元素移动的距离不超过 k, 换句话说就是, 元素正确的位置, 和元素所处的位置不超过 k。
设 0 位置是某一元素的正确的位置, 那么该元素原本的位置只可能在 [0, 6] 之间。（ 0 位置和 6 位置的距离是 6） 所以, 当我们将数组的前 7 个数字依次加入到小根堆中后, 我们能确保 0 位置上的数一定是整个数组中最小的。 将这个数组中最小的数字移出小根堆, 放入数组中的正确位置后, 继续添加元素, 我们就能够依次从小到大的取出元素了。
┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐ ... ┌ ─ ─ ┐
arr: │ ││ ││ ││ ││ ││ ││ ││ ││ ││ │ ... │ │
└ ─0─ ┘└ ─1─ ┘└ ─2─ ┘└ ─3─ ┘└ ─4─ ┘└ ─5─ ┘└ ─6─ ┘└ ─7─ ┘└ ─8─ ┘└ ─9─ ┘ ... └ ─n─ ┘
heap: ┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐
│right││ ││ ││ ││ ││ ││ │ 每取出一个最小值后, 就从剩余的 arr 中拿出一个数到小根堆中。 等同于将 heap 绕着 arr 方向不断移动, 就像窗口一样
└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘
┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐
│right││ ││ ││ ││ ││ ││ │ 每次移动, 都能够找到某位置上正确的数, 或者应该说能够将一个数放到正确的位置上。
└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘
┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐┌ ─ ─ ┐
│right││ ││ ││ ││ ││ ││ │
└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘└ ─ ─ ┘根据上面流程计算时间复杂度： 首先, 数组的每个元素都会添加到小根堆中, 总共会添加 N 次。 每次添加时, 维持小根堆需要消耗的代价是 log(k), 故总的时间复杂度是 O(N*log(k))。
老师代码如下
java
public void sortedArrDistanceLessK(int[] arr, int k) {
// 注意⚠️, 优先级队列是使用小根堆实现的, 它可以提供小根堆的功能
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
// 初始化 heap 小根堆, min 是为了防止 k 大于数组长度
for (; index <= Math.min(arr.length, k); index++) {
// 利用系统黑盒, add 的过程中会自动维持小根堆
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; i++; index++) {
// 不断将元素扔进去
heap.add(arr[index]);
// poll 时的值就是最小值
arr[i] = heap.poll();
}
// 结束时, 说明 arr 中所有数据都已加入到小根堆里了, 所以最后直接将小根堆中的数组一一取出就可以了
while (!heap.isEmpty()) {
arr[i++] = heap.poll()
}
}🍕 堆扩容
堆是存在数组中的, 数组的大小空间是固定的, 当我们将这块数组用完的时候, 就需要申请更大的一块数组, 然后将旧数组的值拷贝到新数组中。这就是堆扩容。
堆扩容是成倍增加的, 比如刚开始申请的数组大小是 64, 当用完的时候, 就再申请一个 128 的, 再用完时就是 256, 512, 1024, ...。
扩容时的代价:
- 假设堆是从 1 开始扩容的, 最终扩容到 N
- 每次扩容是成倍增加的: 1, 2 ,4, 8, ...
- 因为每次扩容时, 需要将内容拷贝到新数组, 所以总拷贝的代价是 O(N)。 (具体计算很简单, 从后往前将拷贝次数加起来: N/2 + N/4 + N/8 + ... 。 根据等比数列求和, 易得时间复杂度为 O(N) )
- 总的扩容的次数为 log(N)。 (这个计算也很简单, 1,2,4,8,..,N, 一共有 logN 个数)
- 总的扩容过程, 拷贝的代价是 O(N), 共扩容了 log(N) 次, 故扩容的总成本为 O(NlogN)
- 将总成本 O(NlogN) 平摊到每个节点, 得: 添加单个节点的代价为 O(NlogN)/N =
O(log(N))
实际运行中, 只会在某一时刻添加新节点时会稍微慢点, 因为此时它需要执行扩容操作, 但将这个代价平摊到添加单个节点时, 成本算是低的。
⚠️, 调用系统提供的堆结构黑盒时, 不一定是最高效的, 因为我们无法修改其黑盒内部的实现逻辑。 这种情况下, 虽然某些需求能够通过系统提供的堆黑盒实现功能, 但成本可能很高。 所以有时候还是得自己手写堆才高效。
🍕 比较器
比较器(或重载比较运算符), 就是定义比较的规则, 对于数字, 比较规则很容易, 但是对于某个对象, 比较的规则就需要手写了, 不然系统默认会是按地址大小比较。
编程语言中, 比较器都有一个统一的潜台词:
- 返回负数的时候，第一个参数排在前面
- 返回正数的时候，第二个参数排在前面
- 前面返回 0 的时候，谁在前面无所谓
✨巧记: 负1正2
比如, 比较器接收的第一个参数是 a, 第二个参数是 b
- 当 a > b 时, 如果想要让大的数排在前面, 就需要返回负数(b-a), 此时第一个参数 a 就会排在前面
- 当 a < b 时, 如果想要让大的数排在前面, 就需要返回正数(b-a), 此时第二个参数 b 就会排在前面
✨巧记: ab升, ba降
🍕 非比较排序算法
前面介绍的排序算法(冒泡, 插入, 选择, 归并, 快速, 堆), 都是基于比较的排序, 他们的时间复杂度通常是 O(N^2) 或 O(N*log(N))。
但实际使用中, 某些情景下可以有更加灵活的排序方法, 这种情况下可以造出时间复杂度为 O(N) 的排序算法。
计数排序
当待排序的数据中, 数据都是正整数, 并且最大值和最小值的差值不大时, 可以考虑采用计数排序。
假设情景: 要对公司员工的年龄进行排序, 因为人的年龄基本是在 (0, 200] 范围内的。
基本思路:
- 创建一个初值为 0, 大小为 200 的数组。
- 遍历员工年龄, 将他们的年龄作为下标, 每次将下标将对应的位置加一
- 最终这个数据就存储了排序后的信息。
故, 对于数据量大, 同时数据范围小的数据, 计数排序的优点非常明显 —— 占用空间少(因为数据范围小, 创建的自然不大), 并且时间复杂度为 O(N)。 最经典的就是, 对公司近万人的年龄排序。
基数排序 1
假设情景: 数字都是正整数
基本思路:
- 定义 10 个桶, 编号依次是 0-9, 因为正整数每一位上的数字只可能是这 10 种结果之一
- 入桶: 初次遍历数组, 先根据当前数个位上的值, 决定将当前数放到哪个桶里面去
- 出桶: 然后将桶中的数字从左往右(从0到9)依次"倒出来", 桶内取出数据要求先进先出。 (即每个桶的结构要能够实现先进先出功能——队列)
- 入桶: 再次遍历数组, 此时根据当前数十位上的值, 决定将当前数放到哪个桶里面去
- 出桶: 继续从左往右, 将桶中的数字按先进先出的方式倒出来
- 不断重复上面过程, 直到根据最大数字的最高位也完成入桶出桶操作。
核心: 先根据个位数入桶出桶, 再根据十位数入桶出桶, ...
举个🌰:
假设有数组 arr
┌─────┬─────┬─────┬─────┬─────┐
arr: │ 017 │ 013 │ 025 │ 100 │ 072 │
└─────┴─────┴─────┴─────┴─────┘
定义 10 个桶如下:
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛
0 1 2 3 4 5 6 7 8 9
每次进出桶时, 根据某一位上的数, 决定将该数字放到哪个桶里面去。
处理位的顺序是: 先个位数, 然后十位数, 以此类推......
从左到右遍历数组 arr
1️⃣
先看个位上的数, 然后将他们依次放入桶中, 如下所示:
┌─────┬─────┬─────┬─────┬─────┐
│ 017 │ 013 │ 025 │ 100 │ 072 │
└ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┘
入桶
┃ 100 ┃ ┃ 013 ┃ ┃ 072 ┃ ┃ ┃ ┃ ┃ ┃ 025 ┃ ┃ ┃ ┃ 017 ┃ ┃ ┃ ┃ ┃
┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛
0 1 2 3 4 5 6 7 8 9
然后按照从左到右的顺序, 将桶中的数字依次取出。 取出桶里的数字时, 依据先进先出的方式取出。 最终数组 arr 更新为:
┌─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┐
arr: │ 100 │ 013 │ 072 │ 025 │ 017 │
└─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┘
2️⃣
按照同样的步骤, 这次是看十位上的数, 然后将他们依次入桶: 如下所示:
┌─────┬─────┬─────┬─────┬─────┐
│ 100 │ 013 │ 072 │ 025 │ 017 │
└ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┘
入桶:
┃ ┃ ┃ 017 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ 100 ┃ ┃ 013 ┃ ┃ 025 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ 072 ┃ ┃ ┃ ┃ ┃
┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛
0 1 2 3 4 5 6 7 8 9
出桶:
┌─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┐
arr: │ 100 │ 013 │ 017 │ 025 │ 072 │
└─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┘
3️⃣
┌─────┬─────┬─────┬─────┬─────┐
│ 100 │ 013 │ 017 │ 025 │ 072 │
└ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┘
入桶:
┃ 072 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ 025 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ 017 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┃ 013 ┃ ┃ 100 ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛ ┗ ━↓━ ┛
0 1 2 3 4 5 6 7 8 9
出桶:
┌─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┬─ ─ ─┐
arr: │ 013 │ 017 │ 025 │ 072 │ 100 │
└─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┴─ ─ ─┘
END基数排序 2 - 代码优化
基数排序 1 中, 创建了 10 个桶, 每个桶都是一个特定的数据结构, 比如队列。
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┗ ━ 0 ━ ┛ ┗ ━ 1 ━ ┛ ┗ ━ 2 ━ ┛ ┗ ━ 3 ━ ┛ ┗ ━ 4 ━ ┛ ┗ ━ 5 ━ ┛ ┗ ━ 6 ━ ┛ ┗ ━ 7 ━ ┛ ┗ ━ 8 ━ ┛ ┗ ━ 9 ━ ┛基数排序 2 中, 不需要创建 10 个桶, 只需要一个长度为 10 的数组 count, 用来统计"数频", 外加一个辅助数组 help, 用来存储每次"出桶"后的数组
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
count: │ │ │ │ │ │ │ │ │ │ │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
┌─────┬──......──┬─────┐
help: │ │ ...... │ │ help 长度与待排序数组相同
└──0──┴──......──┴──?──┘基数排序 2 中的计算 count 数组的方式如下:
- 先看指定位上的值, 然后统计他们的数频, 比如查看个位上的值:
以数组 arr 为例:
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 017 │ 013 │ 025 │ 101 │ 033 │ 072 │
└ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┴ ↑ ┘- 遍历个位上的值
i, 然后count[i]++, 得出个位上各个值出现的频次如下:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
t_count: │ │ 1 │ 1 │ 2 │ │ 1 │ │ 1 │ │ │ 没有写的默认就是 0
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
设 count 下标为 i, i 位置上的元素为 a 的含义为:
数组 arr 中"个位"上值 == i 的数量- 然后对 count 数组求前缀和, 即
count[i] += count[i-1]
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
count: │ 0 │ 1 │ 2 │ 4 │ 4 │ 5 │ 5 │ 6 │ 6 │ 6 │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
此时 count 数组中, 下标 i 上的元素 a 含义变为:
数组 arr 中"个位"上值 <= i 的数量基数排序 2 中的辅助数组 help 计算方式如下:
- 从右到左遍历数组
arr上指定位的值, 比如当前数num的个位上的值为i - 然后以
i为 count 下标, 将对应位置上的值减 1 得到 a, 即a = --count[i] - 最后将
num放到help数组的下标a位置上, 即help[a] = num - 重复上面过程, 直到遍历完数组
arr, 此时相当于完成了一次 入桶出桶 操作 - 完成后记得将
help拷贝到arr数组中。
举个🌰:
要排序的数组 arr
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 017 │ 013 │ 025 │ 101 │ 033 │ 072 │
└─────┴─────┴─────┴─────┴─────┴─────┘
定义 help 数组, 它的大小和 arr 相同:
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ │ │ │ │
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ 这里的值是数组下标
按照前面的步骤, 先遍历个位上的数, 求出 count 数组:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
count: │ 0 │ 1 │ 2 │ 4 │ 4 │ 5 │ 5 │ 6 │ 6 │ 6 │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
从右到左遍历 arr 数组, 比如遇到 72, 个位上是 2, 所以将 count[2]--,
得到 count[2] 的值为 1, 于是将 72 放到 help[1] 上
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 017 │ 013 │ 025 │ 101 │ 033 │ 072 │
└ ↑ ← ↑ ← ↑ ← ↑ ← ↑ ← ↑ ┘
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ 072 │ │ │ │ │ 72, count[2]--; count[2] = 1
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ 072 │ │ 033 │ │ │ 33, count[3]--; count[3] = 3
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 101 │ 072 │ │ 033 │ │ │ 101, count[1]--; count[1] = 0
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 101 │ 072 │ │ 033 │ 025 │ │ 25, count[5]--; count[5] = 4
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 101 │ 072 │ 013 │ 033 │ 025 │ │ 13, count[3]--; count[3] = 2
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 101 │ 072 │ 013 │ 033 │ 025 │ 017 │ 17, count[7]--; count[7] = 5
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
此时成功完成一次进出桶操作, 将 help 拷贝到 arr 中:
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 101 │ 072 │ 013 │ 033 │ 025 │ 017 │
└─────┴─────┴─────┴─────┴─────┴─────┘后面的工作和前面一样, 再继续求取各个位上的数, 然后更新 arr 数组:
对十位上的数执行进出桶:
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 101 │ 072 │ 013 │ 033 │ 025 │ 017 │
└──↑──┴──↑──┴──↑──┴──↑──┴──↑──┴──↑──┘
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
t_count: │ 1 │ 2 │ 1 │ 1 │ │ │ │ 1 │ │ │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
count: │ 1 │ 3 │ 4 │ 5 │ 5 │ 5 │ 5 │ 6 │ 6 │ 6 │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 101 │ 072 │ 013 │ 033 │ 025 │ 017 │
└ ↑ ← ↑ ← ↑ ← ↑ ← ↑ ← ↑ ┘
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ 017 │ │ │ │ 17, count[1]--; count[1] = 2
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ 017 │ 025 │ │ │ 25, count[2]--; count[2] = 3
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ 017 │ 025 │ 033 │ │ 33, count[3]--; count[3] = 4
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ 013 │ 017 │ 025 │ 033 │ │ 13, count[1]--; count[1] = 1
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ 013 │ 017 │ 025 │ 033 │ 072 │ 72, count[7]--; count[7] = 5
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 101 │ 013 │ 017 │ 025 │ 033 │ 072 │ 101, count[0]--; count[7] = 0
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 101 │ 013 │ 017 │ 025 │ 033 │ 072 │
└─────┴─────┴─────┴─────┴─────┴─────┘
对百位上的数执行进出桶:
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 101 │ 013 │ 017 │ 025 │ 033 │ 072 │
└─↑───┴─↑───┴─↑───┴─↑───┴─↑───┴─↑───┘
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
t_count: │ 5 │ 1 │ │ │ │ │ │ │ │ │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
count: │ 5 │ 6 │ 6 │ 6 │ 6 │ 6 │ 6 │ 6 │ 6 │ 6 │
└ 0 ┴ 1 ┴ 2 ┴ 3 ┴ 4 ┴ 5 ┴ 6 ┴ 7 ┴ 8 ┴ 9 ┘
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 101 │ 013 │ 017 │ 025 │ 033 │ 072 │
└ ↑ ←↑ ←↑ ←↑ ←↑ ←↑ ┘
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ │ │ 072 │ │ 072, count[0]--; count[0] = 4
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ │ 033 │ 072 │ │ 033, count[0]--; count[0] = 3
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ │ 025 │ 033 │ 072 │ │ 025, count[0]--; count[0] = 2
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ │ 017 │ 025 │ 033 │ 072 │ │ 017, count[0]--; count[0] = 1
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 013 │ 017 │ 025 │ 033 │ 072 │ │ 013, count[0]--; count[0] = 0
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
help: │ 013 │ 017 │ 025 │ 033 │ 072 │ 101 │ 101, count[1]--; count[1] = 5
└──0──┴──1──┴──2──┴──3──┴──4──┴──5──┘ ↑
┌─────┬─────┬─────┬─────┬─────┬─────┐
arr: │ 013 │ 017 │ 025 │ 033 │ 072 │ 101 │
└─────┴─────┴─────┴─────┴─────┴─────┘
END