写给大家看的算法书-笔记
2019-10-16 本文已影响0人
三文治z
注：个人读《写给大家看的算法书》的粗略笔记，和看的一些博客的总结
一、数据结构
常用的数据结构 Part One
1.链表
- 把各处散乱的数据用绳子一样的结构顺序管理起来的数据结构
2.数组
- 把同类数据紧密排列的数据结构
3.堆栈
- 用于管理像堆积在桌子上的书本一样的数据
- 这种管理方式是：取数据的顺序和存数据的顺序相反（先进后出）
4.队列（等待队列）
- 对数据的管理方式就像是超时收银台前排的队，按照排队的先后顺讯处理数据
- 取数据和存数据的顺序是一致的（先进先出）
5.树（树木的结构）
- 树可以从树干分出两三个枝干，从某一个枝干上又可以分出两三个枝干。像树木结构一样管理数据的数据结构叫做‘树’
常用的数据结构 Part Two
1.堆栈（STACK）
堆栈管理数据的两种操作：
- 写入数据（堆积）操作称作 入栈（PUSH）
- 读取数据操作称作 出栈（POP）
这种数据管理方式被称为 FILO（First In, Last Out）
2.队列（QUEUE）
-最先输入的数据最先输出
这种数据管理方式被称为 FIFO（First In, First Out）
3.链表
- 就像绳子串起来的长串，把离散的数据串起来
- 与二维数组的区别：
1）二维数组：数据是没有间隙紧密排列的
2）链表：数据就像用绳子串起来一样，位置不一定相互紧靠
4.单向链表（只能从前到后检索数据）
- 在链表里，用一根有方向的绳子把数据连接起来的链表叫单向链表
- 单向链表中，每个元素都有以下两种信息：
1）数据
2）指向下一项元素的指针（NEXT 指针） - 1）HEAD 指针：第一个元素的位置信息
2）NEXT 指针：指向下一项元素的指针
3）无效指针：没有下一个元素或没有第一个元素
5.双向链表（可以 从前到后 也可以 从后向前 检索数据）
- 在链表里，用向前和向后两根有方向的绳子来把数据连接起来的链表叫双向链表
- 双向链表的每一个元素都有下面三种信息：
1）数据
2）指向下一项元素的指针
3）指向上一项元素的指针 - 1）HEAD 指针：指向起始元素的指针
2）TAIL 指针：指向末尾元素的指针
3）NEXT 指针：指向下一项元素的指针
4）PREV 指针：指向上一项元素的指针
6.树
- 是一种管理有像树干、树枝、树叶一样关系的数据的数据结构
- 树由节点（顶点）和边（枝）构成 且由一个节点作为起始点即 根节点
1）父节点：旧的节点
2）子节点：延伸出的新节点
3）叶子节点：一个子节点都没有的节点
4）深度：由根节点出发，到达某一个节点，所要经过的边的个数叫做这个节点的深度
7.二叉树（Binay tree）
- 在树型结构中，如果每个父节点只有两个子节点，那么这样的树被称为 二叉树
- 一个父节点的两个子节点分别叫 ‘左子节点’ 和 ‘右子节点’。二叉树可以看作是每一个元素都有两个指向下一个元素的指针的单向链表
- 二叉树还可以用数组表示：
定义某一个父节点的元素索引是 i，其左子节点的元素索引为（i * 2 + 1）,其右子节点的元素索引为（i * 2 + 2）
8.图
- 这种数据结构关注的是两个以上的数据项目之间是如何关联在一起的，并且通过图形一样的方式把这种关联关系表现出来
- 节点：用图来表现的项目
边：表示节点之间关系的线 - 有向图：有节点和有方向的边组成的图
- 加权图：如果一个图的每条边都拥有权重（成本），则这个图就叫加权图
二、算法
例题
1.计算 1~N 的整数的总和
1~2：1+2
1~3：1+2+3
1~4：1+2+3+4
1~5：1+2+3+4+5
通式：1+2+3+......+(N-1)+N
function fn(n) {
let sum = 0;
for(let i = 0;i <= n; i++){
sum += i
}
return sum
}
fn(5); // 15
2.斐波那契数列（兔子数列）
1，1，2，3，5，8，13，21，34，55.......
求第 N 个数字
1） 递归：
function Fibonaci(n) {
if(n==1 || n==2) { return 1 }
return Fibonaci(n-1) + Fibonaci(n-2)
}
2） 优化：尾递归（尾部调用自身）
把之前已经计算好的结果以参数的形式传递过去
function Fibonaci(n, ret1=1, ret2=1) {
if(n==1 || n==2) { return ret2 }
return Fibonaci(n-1, ret2, ret1+ret2)
}
3） for循环版
function Fibonaci(n) {
if(n==1 || n==2) { return 1 }
let ret1 = 1, ret2 = 1
for(let i = 2; i < n; i++){
[ ret1, ret2 ] = [ ret2, ret1+ret2 ]
}
return ret2
}
排序（以下均为升序）
1.桶排序
- 1）先准备‘待排序数组’的‘取值范围个数’的木桶（数组）
2）每个待排序数据都对应一个木桶的标号（数组下标）
3）从木桶的起始元素开始按顺序处理，如果木桶下标对应一个待排序数据，就把这个数据按照出现次数取出来，这样就得到排序好的数据了。 - 总结：就是把数据的出现次数放到下标（index）和数值相同的木桶中。完成这个操作之后，只需从左往右把防止了数据的木桶取出来就可得到原数据的排序。
- 优点：时间复杂度只有 O(m+n)，效率高
缺点：必须准备大量的木桶，需提前知最大值最小值
const arr = [ 8, 3, 5, 9, 2, 3, 0, 8 ]
function BucketSort(list) {
// 创建 [0, 0, ..., 0] 的数组，长度为10-----数组长度要 >(大于) 需排序数组元素的最大值
const newList = Array.from({length:10}).fill(0);
list.forEach(el => newList[el] += 1); // 把数组元素记录在 newList 上
return newList.reduce((pre, el, index) => { // 展开数组
for(let i=0; i<el; i++){
pre.push(pre)
}
return pre
}, [] )
}
2.选择排序
选择最小值（最大值）
- 1）准备一个保存待排序数据的数据，把这个数组分成‘已排序部分’和‘待排序部分’
2）一开始‘已排序部分’是空的，‘待排序部分’是整个数组
3）① 从‘待排序’中找到最小值；
② 把最小值和‘待排序部分’起始位置的元素交换；
③ ‘待排序部分’的起始位置向后移动一位；
④ 循环①~③直至‘待排序部分’只剩一个元素 - 时间复杂度O(n^2)，运算速度很慢
function SelectionSort(list) {
list = [...list]; // 最好不要对原数组操作
const newList = []; // 创建待返回的空数组
while(list.length) { // 循环，当 list.length === 0 时，表示处理完毕
let min = list[0]; // let min = Infinity; 设最小值无穷大 或者 等于 list 中的任意位置都可
let minIndex; // 记录下最小值下标
list.forEach((el, index) => { // 对 list 循环，查找当前 list 最小值
if(el <= min) {
min = el;
minIndex = index;
}
});
newList.push(list[minIndex]); // 将 最小值下标 对应的值 push 进数组
list.splice(minIndex, 1); // 从list内删除这个值
}
return newList
}
3.冒泡排序
核心是：比较相邻的两个元素的大小关系，如果大小关系和排序顺序相反，则交换这两个元素的位置
- 1）‘待排序’的第一个数据和第二个数据相互比较
2）若第一个数据 > 第二个数据，则交换它们的位置
3）进行比较的数据位置向后移动一位 - 时间复杂度O(n^2)
原始
function BubbleSort1(arr){
var i,j,temp;
for(i=0; i<arr.length-1; i++){
for(j=i+1; j<arr.length; j++){
if(arr[i] > arr[j]){
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}
改良：将小的数字如同气泡一样慢慢的浮上表面
function BubbleSort(arr){
for(let i = 0; i < arr.length-1; i++) {
for(let j = arr.length-1; j > i; j--) { // j为从后往前循环
if(arr[j] < arr[j-1]) { // 后面的小于前面的，则交换
[ arr[j-1], arr[j] ] = [ arr[j], arr[j-1] ]
}
}
}
return arr;
}
补充：不使用中间变量，互换两个元素，原型如下：
var a = 10; // 第一个元素
var b = 5; // 下一个元素
if (a > b) {
a = a + b; // a(15) = 10 +5;
b = a - b; // b(10) = 15 - 5;
a = a - b; // a(5) = 15 - 10;
}
// a = a+b 这个得到的是 a 和 b 的和；也就是这一步运行之后当前的a的值就是 a，b 之和。
// b = a-b，既然 a 是他们两个的和，那么 a-b 得出的肯定是最初的a的值；这一步运行之后，b 的只就是原始 a 的值；
// a = a-b，既然 b 是原始 a 的值，a 是原始 a 和原始 b 的和，那么差值肯定就是原始 b的值。
通过es6，可以实现同样的效果：
let arr1 = [ 1, 3 ];
[ 1, 3 ]=[ 3, 1 ];
console.log(arr1); // => [3, 1]
4.插入排序
- 1）首先将数组第1个数看成是一个有序序列
2）将数组的第2个数按照关键字大小插入到这个有序序列中，插入后得到了一包含两个数的有序序列
3）接下来再重复上面的步骤将第3，第4……第n-1个数分别插入到该有序序列中，最终得到一个包含n个数的有序序列
接下来，我们要将这个算法转化为编程语言。 - 假设有一组无序序列 R0, R1, ... , RN-1
① 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列
② 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1
③ 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了
④ 所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1开始向 0 进行扫描 - 时间复杂度O(n^2)
function InsertSort(arr) {
for (let i = 1; i < arr.length; i++){
for (let j = i; j > 0; j--){
// 当前值和之前的每个值进行比较，发现有比当前值小的值就进行重新赋值
if(arr[j] < arr[j-1]){
[ arr[j-1], arr[j] ] = [ arr[j], arr[j-1] ]
}
}
}
return arr;
}
5.快速排序
快速排序的原理：选择一个基准值，一般选择数组的一个值，遍历数组，大的放右边，小的放左边，一样大的放中间。利用递归重复对大的数组和小的数组进行拆分，最后得出排序后的数组。
- 快排的平均时间复杂度是O(n * log n)，但最糟情况的复杂度是O(n ^ 2)
function QuickSort(arr) {
if(arr.length < 2) {
return arr;
} else {
const pivot = arr[0]; // 基准值
const pivotArr = []; // 一样大的放中间
const lowArr= []; // 小的放左边
const hightArr = []; // 大的放右边
arr.forEach(current => {
if(current === pivot) pivotArr.push(current);
else if(current > pivot) hightArr.push(current);
else lowArr.push(current);
})
return quickSort(lowArr).concat(pivotArr, quickSort(hightArr));
}
}
