9.5 最短路径算法 9.5.1 Dijkstra 算法
相应的邻接矩阵
注意, 之前的图都是未加权的图, 这个例子是加权图
之前图用的都是邻接链表来表示, 这个例子是用邻接矩阵来表示的
书中写的封装有点问题,
- 首先是graph 权重有写错一个地方, 是不够细心的问题
- 这里明显用的是 邻接矩阵, graph 定义在了全局上,
但在dikstra 函数竟然 用this.graph 的方式进行调用. 有点问题.
当然在github 上可能有完整的上下文, 我没去看,
我们先把几个小问题稍微改一下
var graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 2, 4, 2, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 2],
[0, 0, 0, 3, 0, 2],
[0, 0, 0, 0, 0, 0]
];
var INF = Number.MAX_SAFE_INTEGER;
var dijkstra = function(src) {
var dist = [],
visited = [],
length = this.graph.length;
for(var i = 0; i < length; i++) { //{1}
dist[i] = INF; // infinity? 无穷大
visited[i] = false;
}
dist[src] = 0; //{2}
for(var i = 0; i < length - 1; i++) { //{3}
var u = minDistance(dist, visited); //{4} / 这个函数是找出 目前最近元素是谁,同时这个点到src点的最短距离就是确定的了.
visited[u] = true; //{5}
for(var v = 0; v < length; v++) {/ 这一段是 更新每一阶段中 离 src点的最短距离
if(!visited[v] &&
graph[u][v] != 0 && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) { //{6}
dist[v] = dist[u] + graph[u][v]; //{7}
}
}
}
return dist; //{8}
};
var minDistance = function(dist, visited) {
var min = INF,
minIndex = -1;
for(var v = 0; v < dist.length; v++) {
if(visited[v] == false && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
};
首先要搞清楚 src 是什么? 调用方式是什么
0 代表图中的 A 同理 1 : B , 2 : C ....
上面测试中的 9007199254740991 其实就是个无穷大的数.
所以返回的结果确实能够回答这个功能的需求.
准备工作到这里, 问题是, 即使是这样, 这段代码还是有点难读懂.
百度了一下
简单易懂——Dijkstra算法讲解
这里用图 和步骤 讲解了一下,
再次感到, 写代码时, 不只是要懂概念和数学原理, 还需要这种图来进行辅助思考,
否则至少我的大脑是很难有效思考的.
总算有点明白是怎么回事了,
相比于讲解,
这个代码写得应该是经过了很多次的优化.应该算是比较精巧的结构了.
花了这么长时间才看懂, 也不算很冤枉.
这段代码本身有很多地方值得学习, 还真的挺难消化的.
1.
首先他是用了两个数组 dist 和 visited
即, 两者实际上通过 同一个i 互相之间是有联系的.
一般我想要达到这个效果 很有可能采取的结构是
item1 = {
dist : distValue,
visited : true | false
}
但这样做的话, 层级会深一层, 后续遍历操作会非常不方便.
按照这种思路,我们简单实践一下
我常用的思路是这样的
var arr = [
{
name : 'mike',
sex : "male",
age : 18,
visit : false
},
{
name : 'peter',
sex : "mail",
age : 20,
visit : false
},
{
name : 'kity',
sex : "femail",
age : 16,
visit : false
},
]
如果按照上面的思路 则可以改成这样
var name = ['mike','peter','kity'];
var sex = ['male','mail','femail'];
var age = [18,20,16];
var visit = [false,false,false];
这几个数组之间看似没有关系, 但严格按照顺序排列
可能的优点和缺点, 虽然不是很清楚,
目前第一印象来看,
优点是 : 层级比较浅, 如果要对单个属性组进行操作可能会更方便?
缺点是 : 联系是看不见的 index ,这种数据关系似乎不是很牢靠?
按照这个思路, 也可以应用在对象上?
第一种
var obj = {
a : {
name : 'mike',
sex : "male",
age : 18,
visit : false
},
b : {
name : 'peter',
sex : "mail",
age : 20,
visit : false
},
c : {
name : 'kity',
sex : "femail",
age : 16,
visit : false
},
}
第二种
var name = {a : 'mike', b : 'peter',c : 'kity'};
var sex = {a : 'male',b : 'mail',c : 'femail'};
var age = {a : 18,b : 20,c : 16};
var visit = [a : false,b : false,c : false];
这样做相比 数组形式而言, 优点是似乎稳定性还是比较强的,
缺点是 似乎变得更加复杂?
想象中的用法比较
myname is obj.a.name , im a obj.a.sex, and obj.a.age years old do you like me ? obj.a.visit
myname is name['a'] , im a sex['a'], and age['a'] years old do you like me ? visit['a']
确实层级低了一层, 但第一种情况时我们完全可以用一个中间变量来接收 如 var a = obj.a
如果联想之前学习字典还是集合时的变量私有化的话,
其实第二种可能对数据的保护更有用?
因为第一种而言, 得到了一个 a 对象, 能够访问和修改很多值.
而第二种而言, 我即使得到了a 字符串, 想要完成修改, 还需要得到 name,age,visit 等对象
才能进行访问和修改? 所以安全性更高一点?
2.
这是我头一回遇到用 INF来进行数据初始化的代码,
求的是最短, 所以初始化成无穷大.
3.
这个代码绝对(我猜几乎不可能)是通过光写代码进行调整能够写出来的,
必定是从数学上, 或者是从图上发现了规律, 发现了方法之后,
才将其翻译成了 代码.
当然也许这本书中的所有代码都是这样的,
又或者所有代码本都应该是这样的.
我想说的是, 画图 和 写出概念之后 对着图和概念进行思考,
肯定比 写一些 代码之后, 对着代码思考 要清晰很多?!
因为天然的代码的表达的似乎都是线性的表达,变量和变量之间的关系,
变量本身的样子,
都是不直观的,
而画成图,
特别是 像 二维数组 用 矩阵图来进行 描述时,
整个关系是立体的, 比较容易理解的.
说了这么多边边角角, 我还是无法消化这个函数,
消化率可能只打到百分之40?
只知道, 这个函数能够求 最短路径,呵呵呵...
9.5.2 Floyd-Warshall 算法
var floydWarshall = function() {
var dist = [],
length = graph.length,
i, j, k;
for(i = 0; i < length; i++) { //{1}
dist[i] = [];
for(j = 0; j < length; j++) {
dist[i][j] = graph[i][j];
}
}
for(k = 0; k < length; k++) { //{2}
for(i = 0; i < length; i++) {
for(j = 0; j < length; j++) {
if(dist[i][k] + dist[k][j] < dist[i][j]) { //{3}
dist[i][j] = dist[i][k] + dist[k][j]; //{4}
}
}
}
}
return dist;
};
说实话, 文章当中 这一节的描述真的是不够,
只说 核心就是 行{3}, 一头雾水.
百度一下
最短路径Floyd算法【图文详解】
跟着读了两遍, 明白是什么意思了.(第一部分的矩阵运算知识,我就呵呵了,回头有机会再补这部分知识吧)
其实核心确实是行{3} 意思是这样,先看下面这个表
从2 到 3 直接的距离是无穷大(就是没有路)
如果从2 先去1 再去 3 则距离是 2 + 7 = 9, 也就是说这个距离比直接去的距离短.
把点1 当做中间火车站, 然后计算 间接距离和 直接距离的比较 哪个小, 哪个就替换表中的值.
(上面的默认值都是直接距离, 我们要填的是最短(更短)距离)
点1完事之后, 让点2 做中间火车站,
我这个图的数据没更新, 应该是在上一个的基础上做的操作.
如果真的有人会读这一段, 你千万不要觉得很难,
一定是我描述的太烂的结果, 你可以看链接.
其实我个人觉得, 我觉我懂了的时候, 其实是 这个计算过程是,
看着这张图的时候, 会有一种看动画的感觉, 哪个数据和哪个数据结合,然后跟谁比较,
看着这张图, 他是一种动画, 会觉得很简单.
但一开始是先看代码, 然后看这些解说的时候, 因为没有建立这个动画,
所以会感觉很难.
其实完全没有必要下一个死结论:觉得这是高级知识,肯定是比较难的.
因为我们要用一个语言, 非常线性的, 方式, 把一个动画进行精确描述的时候,
一定会变得异常复杂,且"难"以理解.
想想看, 如果我们学一个苹果的时候,
关于苹果的形状, 味道, 颜色, 全部用语言来描述,
而不提供实物, 也不用画图, 也不用什么比喻时,
为了精确的,准确的描述苹果是什么,
我们肯定是会把苹果描述的像是大学里的高级知识,
(我不是100%确信会这样,但我几乎这么认为)
但实际上, 苹果是什么,
有时候, 我们确实无法像,大学教授, 生物,植物,水果各类专家一样 很准确,精确的描述,
但我们毫不怀疑, 我们知道苹果是什么, 对吧?
起码你心里不会觉得这是个很难的知识吧? 不会畏惧一个苹果,对吗?
如果我们不畏惧一个苹果是什么,这样一个问题,
那么是否有理由,有勇气去相信, 很多问题,实际上都比我们想象的要简单.
之所以难就是因为很多东西缺乏想象时,光用语言描述我们处理起来费劲.
另一个主要原因是, 我们对知识进行了一种从低到高的等级划分.
诚然, 有些知识 必然是以另外一些知识为 储备,为 基础 才能进行学习.
但这并不表明, 这些知识会比 其 基础知识 会更难.
我们在学习这个知识之前就已经"畏惧"了, 所以遇到"难" 的地方,
我们会放大这种感觉, 会沮丧, 会烦躁.
如果你能学会中文,
(很多外国人是比你说得差很多的, 而且再怎么学都可能达不到你的水平)
你能学会这么"难"的语言,
理论上, 你也能够学会其他知识不是嘛?
唠唠叨叨,唠唠叨叨,
我是真心不想看自己的文字第二遍,
原因很简单,
包括这句, 以及上面三句, 都是废话, 废话太多了.
废话多, 就会对找到核心逻辑产生认知成本的上升.
上面这一大片的废话,核心主题就是,
管他什么拓扑,散列,Floyd, 乱七八糟的吓人的高级词汇,
没必要被吓着.如果我真的没能学会, 肯定是作者水平烂.不然肯定能学会的.
回到正题, 我们重新看一下两个算法的思路
Dijkstra ,Floyd
书中说, Dijkstra算法体现的是什么贪心算法
Floyd 算法体现的是动态规划算法
我们这里不需要找到什么解答, 只是简单留出些问题思考一下,
回头如果遇到解答的知识, 对理解起来可能也有帮助.
不过才重新注意到,Dijkstra 算法求的是 src(某一点)到其他点的最短距离,
而Floyd 算法求的是一个表, 能够表示 图中任意两点的最短距离.
所以一个叫 单源最短距离问题, 一个叫多元最短距离问题.
9.6 最小生成树（MST）
9.6.1 Prim 算法
求加权无向连通图的MST的贪心算法
var prim = function() {
var parent = [],
key = [],
visited = [];
length = graph.length,
i;
for(i = 0; i < length; i++) { //{1}
key[i] = INF;
visited[i] = false;
}
key[0] = 0; //{2}
parent[0] = -1;
for(i = 0; i < length - 1; i++) { //{3}
var u = minKey(key, visited); //{4}
visited[u] = true; //{5}
for(var v = 0; v < length; v++) {
if(graph[u][v] && visited[v] == false &&
graph[u][v] < key[v]) { //{6}
parent[v] = u; //{7}
key[v] = graph[u][v]; //{8}
}
}
}
return parent; //{9}
};
var minKey = function(dist, visited) {
var min = INF,
minIndex = -1;
for(var v = 0; v < dist.length; v++) {
if(visited[v] == false && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
};
从形式上讲 prim 的 代码和Dijkstra 算法非常相似,
所以刚开始我以为能比较快的进行理解.实际并没有, 也花了比较长的时间
百度了一下
prim算法
算法思路：从某个顶点开始，假设v0，此时v0属于最小生成树结点中的一个元素，该集合假设u，剩下的V-v0为待判定的点，此时选取u中的顶点到V-v0中顶点的一个路径最小的边，并且将其中非u中的顶点加入到u中，循环直到u中的顶点包含图所有的顶点为止。
这位博主说得比较清楚了, 但我还是花了一些时间才感觉明白了.
我只能形容为非常的巧妙,
实际上无论是 Dijkstra 还是 prim ,
首先是从数学上的思路就很巧妙, 或者比较难想到(或者总结一个方法比较难想到)
其次是翻译成代码的过程也很巧妙.
实际上 从数学转到 代码的过程还比较容易理解,
荣代码转到数组 就比较困难.
总之, 我只能算了解有这样一个算法, 能够求出最小生成树了.
想要完全理解掌握,这个的思路,还不能够.
Kruskal 算法
var kruskal = function() {
var length = graph.length,
parent = [],
cost,
ne = 0,
a, b, u, v, i, j, min;
cost = initializeCost(); //{1}
while(ne < length - 1) { //{2}
for(i = 0, min = INF; i < length; i++) { //{3}
for(j = 0; j < length; j++) {
if(cost[i][j] < min) {
min = cost[i][j];
u = i;
v = j;
}
}
}
u = find(u, parent); //{4}
v = find(v, parent); //{5}
if(union(u, v, parent)) { //{6}
ne++;
}
cost[u][v] = cost[v][u] = INF; //{7}
}
return parent;
}
var find = function(i, parent) {
while(parent[i]) {
i = parent[i];
}
return i;
};
var union = function(i, j, parent) {
if(i != j) {
parent[j] = i;
return true;
}
return false;
};
这个代码也是一样, 看着也没几行代码,
每一块的代码也都感觉挺简单, 能看懂,
但组合在一起的时候, 到底发生了什么事情?
为什么能够达到这种效果?
就很难理解!
还是要百度一下
最小生成树之克鲁斯卡尔（Kruskal）算法
这位博主写得相当好了, 特别是其中一张图,
非常简洁的把核心思路讲了出来,
不过要理解什么是连通分量,
连通分量就是, 一张图中, 可能存在互相无法访问的路径, 此时这两个路径就是不同的连通分量
连通分量-百度百科
image.png
然后是张神图,我们贴过来
这几个算法,确实很难完全消化,
咱们等下回读第三遍, 或者第四遍的时候, 再进行思考进行消化.
第十章 排序和搜索算法
辅助的数据结构(书里似乎喜欢用面向对象的形式?)
function ArrayList() {
var array = []; //{1}
this.insert = function(item) { //{2}
array.push(item);
};
this.toString = function() { //{3}
return array.join();
};
}
冒泡排序
这个函数的功能很简单, 就是交换一下数值, 或者也可以称之为换一下位置.
var swap = function(array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
this.bubbleSort = function() {
var length = array.length; //{1}
for(var i = 0; i < length; i++) { //{2} / 双层循环则是, 每次把最大的往后面移送过去
for(var j = 0; j < length - 1; j++) { //{3}/只有一层循环时, 表示把最大放在最后面
if(array[j] > array[j + 1]) { //{4}
swap(array, j, j + 1); //{5}
}
}
}
};
改进版
this.modifiedBubbleSort = function() {
var length = array.length;
for(var i = 0; i < length; i++) {
for(var j = 0; j < length - 1 - i; j++) { //{1}
if(array[j] > array[j + 1]) {
swap(j, j + 1);
}
}
}
};
发现行{1} 多了一个 - i , 其实可以理解, 因为 i值正好表示 已经完成移位的数量,
这些已经排到后面的都已经经过了比较, 没必要再比一次.
10.1.2 选择排序
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并
将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。
this.selectionSort = function() {
var length = array.length, //{1}
indexMin;
for(var i = 0; i < length - 1; i++) { //{2}
indexMin = i; //{3}
for(var j = i; j < length; j++) { //{4}
if(array[indexMin] > array[j]) { //{5}
indexMin = j; //{6}
}
}
if(i !== indexMin) { //{7}
swap(i, indexMin);
}
}
};
这个也比较好理解,
不过先存一个序号, 最后再进行交换, 之前写过挺多次 排序这个倒是没想到.
10.1.3 插入排序
this.insertionSort = function() {
var length = array.length, //{1}
j, temp;
for(var i = 1; i < length; i++) { //{2}
j = i; //{3}
temp = array[i]; //{4}
while(j > 0 && array[j - 1] > temp) { //{5}
array[j] = array[j - 1]; //{6}
j--;
}
array[j] = temp; //{7}
}
};
这个是理解了,但确实不太好想.反正就想象成扑克牌排序就理解了.
必须从第二个位置开始,把一张抽出来(相当于放在了 temp)
然后根据大小比较决定前面的牌是否移位.
然后再把牌放回去(相当于把 temp 赋值给 array[j])
10.1.4 归并排序
归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一
个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
this.mergeSort = function() {
array = mergeSortRec(array);/ 这里再次可以看到, 想要用递归 最好把 对象调用方式改成 函数传参形式. 起码这本书应该是这么隐式的推荐我们这样做.
};
var mergeSortRec = function(array) {
var length = array.length;
if(length === 1) { //{1}
return array; //{2}
}
var mid = Math.floor(length / 2), //{3}
left = array.slice(0, mid), //{4}
right = array.slice(mid, length); //{5}
return merge(mergeSortRec(left), mergeSortRec(right)); //{6}
};
var merge = function(left, right) {/ 合起来的时候进行排序.
var result = [], // {7}
il = 0,
ir = 0;
while(il < left.length && ir < right.length) { // {8}/ 这三个循环用得很太漂亮了
if(left[il] < right[ir]) {
result.push(left[il++]); // {9}
} else {
result.push(right[ir++]); // {10}
}
}
while(il < left.length) { // {11}
result.push(left[il++]);
}
while(ir < right.length) { // {12}
result.push(right[ir++]);
}
return result; // {13}
};
之前的方法相当于我要操作一张牌, 我手里必须要拿着所有的牌,(遍历整个数组)
而归并排序则是先把一组牌全部打散, 放在地上,
第一阶段我操作一张牌, 只需要从地上拿起两张牌即可,
第二阶段我操作一张牌, 只需要手里拿着2组,即四张牌即可,(有可能是奇数)
...
只有在最后的时候,我手里拿着全部的牌进行操作.
所以性能会更好?
大概是这么理解的, 总体意思就是, 先把牌全部放在地上.
10.1.5 快速排序
快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复
杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分
为较小的数组（但它没有像归并排序那样将它们分割开）。
快速排序比到目前为止你学过的其他排序算法要复杂一些。让我们一步步地来学习。
(1) 首先，从数组中选择中间一项作为主元。
(2) 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指
针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交
换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之
前，而比主元大的值都排在主元之后。这一步叫作划分操作。
(3) 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的
子数组）重复之前的两个步骤，直至数组已完全排序。
this.quickSort = function() {
quick(array, 0, array.length - 1);
};
var quick = function(array, left, right) {
var index; //{1}
if(array.length > 1) { //{2}
index = partition(array, left, right); //{3}
if(left < index - 1) { //{4}
quick(array, left, index - 1); //{5}
}
if(index < right) { //{6}
quick(array, index, right); //{7}
}
}
};
var partition = function(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)], //{8}
i = left, //{9}
j = right; //{10}
while(i <= j) { //{11}
while(array[i] < pivot) { //{12}
i++;
}
while(array[j] > pivot) { //{13}
j--;
}
if(i <= j) { //{14}
swap(array, i, j); //{15}
i++;
j--;
}
}
return i; //{16}
};
具体图的描述 可以取看这个书, 看着图对照代码, 也算是看懂了,
这跟我之前在渡一学过的快速排序很不一样啊!
var arr = [5,6,9,5,18,9,7];
function quickSort (arr) {
if (arr.length <= 1) {
return arr
}
var item = arr[0];
var leftArr = [], rightArr = [];
for(var i = 1; i < arr.length; i++) {
if (arr[i] <= item) {
leftArr.push(arr[i])
} else{
rightArr.push(arr[i])
}
}
return quickSort(leftArr).concat([item],quickSort(rightArr))
}
console.log(quickSort(arr))
还好还好, 我竟然还没忘得干净.
难道这个不是快速排序?
难道是我的错觉? 我怎么感觉两个快速排序这么不一样呢?
百度了一下,
快速排序（过程图解）
绝对是大神,讲得由浅入深,我似乎明白了!(哈哈哈哈,我真是个小白)
我觉得核心是这一句,
快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了
比冒泡快的原因则是这一句
速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的,...冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。
书中的基准值选的是 中间的, 这位大神的例子中基准值选的是数组第一个,
所以基准值的选择方式无关紧要,
再偷一下这位大神的图片
按照这个思路来看, 实际上 书中的版本和渡一教的版本, 核心思路是一样的?
都是每次让基准值归位?
不知道有没有什么性能上的差异, 但目测是, 渡一的版本明显更加简洁, 且可读性好吧.
10.1.6 堆排序
var buildHeap = function(array) {
var heapSize = array.length;
for(var i = Math.floor(array.length / 2); i >= 0; i--) {
heapify(array, heapSize, i);
}
};
var heapify = function(array, heapSize, i) {
var left = i * 2 + 1,
right = i * 2 + 2,
largest = i;
if(left < heapSize && array[left] > array[largest]) {
largest = left;
}
if(right < heapSize && array[right] > array[largest]) {
largest = right;
}
if(largest !== i) {
swap(array, i, largest);
heapify(array, heapSize, largest);
}
};
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp
}
heapSort(arr);
说实话, 书中这部分弄得不是很好, 原因在于,
整本书,之前压根没提到什么是 堆结构,
也没个介绍, 突然就来构建一个堆结构,
显得有点缺乏诚意.
百度了一下,
又是个大神!
图解排序算法(三)之堆排序
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
我的理解是, 把一个数组根据序号可以看成是个二叉树,
然后根据构建大顶堆(小顶堆)的方式 找出最大值(最小值), 取出该元素之后,
对剩余的元素再次进行 构建 的方式找出最大值,
依次类推最后就能完成排序了.
哦~ 想了大半天, 对照着图,终于理解了.
我觉得代码中最需要理解的是 行{10},
这个 length / 2 取整后的数字决定了从哪里开始,直接定位到倒数第二层的最右面,
i-- 表示 这个指针在每一层都会向左移动, 依次往上走, 最后能够得出最大值(最小值).
非常巧妙, 说这个也是选择排序的一种,
之前的选择排序是 遍历比较 得出最小的 然后放入该位置,
看来选择排序的概念就是先选出最大值或者最小值.
我虽然对这个复杂度的计算没什么基础, 所以没什么感觉,
但把一个数组用序号,来对号入座一个二叉树,
之前没什么感觉,
现在觉得, 他至少天然的做了一件事情,
他把 数组之间的 相邻关系给 重新诠释了
比如 从 数组的角度来看 [1,2,3,4,5,6],
1 的旁边就是2, 2 的旁边就是 1 或者3,
但用二叉树进行构建之后,
1 的下面是 2 和 3 , 2的下面是4 和 5
严格来讲, 对于2 来说 他多了好几个关系,
从树的角度说, 1, 4,5 都是有直接关系的, 从序号的角度说, 1 和 3 都是有关系的.
用数学关系来讲, i 和 2i 以及 2i + 1 产生了紧密的关系
如果按照这个说法, 实际上也可以构建三叉树,四叉树,
也就是说, 一个数组可以用不同的树来看待?
10.1.7 计数排序、桶排序和基数排序（分布式排序）
这一部分书中没有介绍
百度了一下
数据结构与算法——计数排序、桶排序、基数排序
这部分内容, 等我们看书第三遍或者第四遍的时候再考虑吧.
另外, 这位博主虽然用的是 java , 但数据结构与算法相关的东西写得很全面, 我觉得可以做参考.
