结构化编程
一行一行执行
有条件控制语句 if…else…
有循环控制语句 while(exp) do…
伪代码
不纠结语法细节，语法自己定
可以体会语言设计者的想法，因为语法是自定的
流程图 ==一轮选择排序选出最小值==
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 st=>start: 开始 ed=>end: 打印最小值min as1=>operation: a = {'0':23,'1':34,'2':45,'3':123,'4':213,'length':5} as2=>operation: min = a[0] as3=>operation: index = 1(不需要从索引0开始) cond1=>condition: index<a['length'] cond2=>condition: a[index]<min op1=>operation: min=a[index] op2=>operation: index=index+1 st->as1->as2->as3->cond1 cond1(yes)->cond2 cond1(no)->ed cond2(yes)->op1->op2 cond2(no)->op2 op2->cond1
==冒泡排序==
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 st=>start: 开始 ed=>end: 结束 input=>inputoutput: 输入数组a initt1=>operation: (轮次)turn = 0 opt1=>operation: turn = turn + 1 condt=>condition: turn < a.length initi1=>operation: (数组索引下标)index = 0 condi=>condition: index < a.length - 1 condbc=>condition: a[index+1] < a[index] opswap=>operation: 交换a[index]和a[index+1] temp = a[index] a[index] = a[index+1] a[index+1] = temp opi1=>operation: index = index + 1 print=>operation: Print a st->initt1->opt1->condt condt(no)->print->ed condt(yes)->initi1->condi condi(no)->opt1 condi(yes)->condbc condbc(no)->opi1 condbc(yes)->opswap->opi1 opi1->condi
交换a[index]和a[index+1]
算法
输入: 一个算法必须有0个或以上输入量
输出: 一个算法必须有一个或以上输出量，输出量是算法计算的结果。
明确性: 算法的描述必须无起义，保证算法的实际执行结果精确地匹配要求或期望，通常要求实际运行结果是确定的。
有限性: 依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
数据结构 数据的结构。
解决一个跟数据相关的问题
分析这个问题，先想出对应的数据结构
分析数据结构，再相处算法
数据结构和算法是互相依存、不可分开的
==算法大分类 ==
分治法: 把一个问题分区成互相独立的多个部分分别求解，这种求解思路便于进行并行计算。
动态规划法: 当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
(把局部最优解看作最优解)
贪婪算法: 常见的近似求解思路。当文字的整体最优解不是(或无法证明是)由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
(把眼前看到的最好办法看作最优解(短视算法))
线性规划法:
简并法: 把一个问题通过逻辑或数学推理，简化成与之等价或近似的、相对简单的模型，进而求解。
前端最主要使用分治法——分而治之
排序算法
体育委员两两摸头法 ==冒泡排序==
体育老师一指禅法 ==选择排序==
起扑克牌法 ==插入排序==
强迫症收扑克牌法 ==计数排序==
桶排序
基数排序(LSD低位优先(适用于位数少) | MSD高位优先(位数多时效率更优))
快速排序 / 随机快排
==冒泡排序 ==
索引从小到大,顺序都是从左向右,
若从小到大排,则每一轮后会将最大的推到最最右边,站定了
若从大到小排,则每一轮后会将最小的推到最最右边,站定了
精髓
每次比较都是比较两两相邻的,一个一个向上挤,就像泡泡一样,把最大的(看需求)挤到最上面,然后浮出水面(即确定位置不动了).
n即数组的长度,有几个数 假设轮次为t,则第t轮需要比较n-t次
第一轮后只是将最大的推到最右边(在相邻的两个数之间画圆弧,一共需要比较n-1次)
第二轮将第二大的推到最右边(第一大已经固定位置不动了,这里的最右边是指第一大的左边)
第n-1轮将第n-1大的推到最右边(这时剩下两个数了,比较(n-(n-1)次,即1次)
不需要第n轮了,因为只剩下第n大的数了(即最小的数)
==选择排序 ==
从头比到尾,不是只比较相邻的两个数
设置一个变量min,最小的赋值给min
第一轮过后,把min挪到了最左边,与之前的第一个数交换位置
第二轮过后,把min挪到最左边的右边,即第二个位置
精髓
从小到大排,每一轮找出最小的,换到最左边
与冒泡正好相反,冒泡的从小到大是每一轮找出最大的,顶到最右边
找出最小的时候不是立刻换位置,是一轮完了之后再换位置
选择排序伪代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 输入数组a turn = 1 while turn < a.length min = a[turn-1] index = turn while index < a.length (注意此处不是轮次而是遍历,所以每个数都要看,所以是length不是length-1) if a[index] < min min = a[index] min_index = index else //do nothing end index = index + 1 end a[turn-1]与a[min_index]换位置 turn = turn + 1 end
计数排序(收扑克牌法)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 输入一个数组a， 找出数组a中的最小值amin和最大值amax， 创建一个计数数组b，b的长度length=amax+1(这样设置是为了下方代码能方便将a元素值作为b索引；若将length设为amax-amin+1能更节省空间||注意:在js中，若有一个空数组，设置a[6]=1，则数组为a[empty×6,1]，长度为7，所以还是用amax+1吧)， 数组b所有元素的值初始化为0 a数组元素的值作为b数组索引，a数组元素出现的次数作为b数组元素的值。 for(index=0;index<a.length;index++){ for(i = 0;i < b.length;i++){ if a[index] == i b[i] = b[i] + 1 end } } 输出 for(j=0;j<b.length;j++){ for(k=0;k<b[j];k++){ print j } }
计数排序流程图
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 st=>start: 开始 ed=>end: 结束 input=>inputoutput: 输入数组a init-arrayb=>operation: 创建一个计数数组b，b的长度length=max(a)+1，b中所有元素值=0 output=>inputoutput: Print j 从小到大打印排序后的数组元素 st->input->init-arrayb output->ed init1=>operation: index=0,i=0 init2=>operation: j=0,k=0 cond-a1=>condition: index<a.length cond-a2=>condition: i<b.length cond-cmp=>condition: a[index]==i op-a1=>operation: index++ op-a2=>operation: i++ op-b+=>operation: b[i]++ cond-b1=>condition: j<b.length cond-b2=>condition: k<b[j] op-b1=>operation: j++ op-b2=>operation: k++ init-arrayb->init1->cond-a1 cond-a1(yes)->cond-a2 cond-a2(yes)->cond-cmp cond-cmp(yes)->op-b+->op-a2->cond-a2 cond-cmp(no)->op-a2->cond-a2 cond-a2(no)->op-a1->cond-a1 cond-a1(no)->init2->cond-b1 cond-b1(yes)->cond-b2 cond-b2(yes)->output->op-b2->cond-b2 cond-b2(no)->op-b1->cond-b1 cond-b1(no)->ed
若设置b.length = amax - amin + 1
则可以用这个判断，而不是将b数组所有元素置为0
number为a数组元素的值，因为将a数组元素的值作为b数组索引，所以肯定至少出现过一次
1 2 3 4 5 6 7 8 9 a <- { '0':0, '1':2, '2':1, '3':56, '4':4, '5':67, '6':3, }
1 2 3 4 5 6 7 8 9 index = 0 while(index < a.length) number = a[index] if b[number] == undefined // b[number] 不存在/未定义，则置为1，说明至少出现过1次， b[number] = 1 else b[number] <- b[number] + 1 //之前出现过了，则再出现就加1 end index = index + 1 end
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 index2 <- 0 max <- findMax(a) // 最大值67 newArr <- {} while index2 < max + 1 count <- b[index2] if count != undefined // 不等于undefined代表count值存在(被赋值过)，至少为1，则可以push countIndex <- 0 //此处循环代表计数个数有几个，就打印几次出来，count值代表b数组元素的值，即a数组元素出现次数计数 while countIndex < count newArr.push(index2) countIndex <- countIndex + 1 end end index2 <- index2 + 1 end print newArr
数据结构
==哈希==
key value 键值对
桶排序，入桶 出桶
所有桶组成一个哈希
计数排序，浪费更多桶，浪费空间版桶排序，弱化版桶排序
适用于排范围较小的正整数，例如年龄、学号等
缺点：
需要hash，占空间
无法排序负数和小数(负数优化下其实可以排，全都加上一个正数)
桶排序，升级版计数排序
节省空间，可以更灵活地安排桶，但要做二次排序，
例如高考分数
基数排序，10个桶，0~9，适用于排序更大范围的整数，比如上万上十万，不适合用计数排序或桶排序
依次对比个位、十位、百位、千位……
==队列==
push进队，shift出队
var queue = []
q.push(‘张三’)
q.push(‘李四’)
q.push(‘王五’)
q.shift() //出队，先进的先出，第一次出队的是张三，shift一次后数组减少一个元素
‘张三’
==栈==
先进后出
可以用数组实现
举例：盗梦空间，电梯，冰箱，汉诺塔
push入栈，pop弹栈
var stack = []
stack.push(‘第一层梦’)
stack.push(‘第二层梦’)
stack.push(‘第三层梦’)
stack.pop() //出栈，弹出
‘第三层梦’
==链表==
一个哈希指向另一个哈希，再指向另另一个哈希,
多个哈希连接起来
数组无法直接删除中间某一项(操作较复杂)，链表可以
可用哈希(JS里用对象object表示哈希)实现链表
head、node概念，链表头也是节点
取链表中某一项很麻烦，chain.next.next.next…….next
删除数组的一项操作很多，删除一个后还要将后续元素提前，然后将长度-1
链表删除一项很简单很方便
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var chain = { value:0, next:{ value:2, next:{ value:1, next:undefined } } } 3项的链表 0 -> 2 -> 1 想删除第二项，让第一项直接指向第三项即可 chain.next = chain.next.next
==树==
举例：层级结构、DOM、堆排序
概念：层数、深度、节点个数 | 深度即为总层数
操作：增删改查
二叉树 第i层，最多2^i-1^个节点；前i层，总节点数最多为2^i^-1个节点
取第i层第1个节点的数据，a[2^i-1^-1]；取第i层第n个节点，a[2^i-1^-1+(n-1)] (完全二叉树才可以用这个方式取)
满二叉树 (长满了叶子的二叉树，满二叉树也是完全二叉树)
完全二叉树 (除了最后一层，其他层都长满叶子；最后一层右边缺少连续若干叶子，即节点是连续的，中间没有断开)
满二叉树和完全二叉树可以用数组来实现
B树 | 红黑树 | AVL树
其他树可以用哈希(对象)来实现
断子绝孙的节点是叶子节点，没有后代
最顶部节点-根节点
==堆==
堆可以看作一棵完全二叉树
最大堆(用的多)
堆排序
第一轮将所有数变成最大堆，则最大数到了根节点位置，把他取走
第二轮将剩余数变成最大堆，则次大的数到了根节点位置，把他取走
第三轮…
第n轮…
相当于从大到小排序
做了一次最大堆调整，有节点位置换了后，新的父亲要和后面的新儿子再次对比
最小堆
最大堆调整：
两个儿子对比，最大的儿子和父亲比，如果赢了则调上去替换掉父亲
已知儿子节点下标i，parent(i)=floor(i/2) 向下取整
已知父亲节点下标i，
儿子节点left(i)=2i，左子节点下标
儿子节点right(i)=2i+1，右子节点下标
第n层的左边第一个节点下标 i = 2^n-1^
第n层最右边的节点下标 i = 2^n^ - 1 （即第n+1层的上一个节点,即2^(n+1)-1^-1)
