基本排序
蛮力法
冒泡排序 : 每一次扫描列表都找出一个最大值沉到底部。[ 在位，稳定 ] 最好是O(n) 最差是O(n^2)
选择排序：每一次扫描列表都找出一个最小的值放到无序区的首部。对数组A做第i次扫描，找出最小值A[min]，和A[i]做交换。 [ 在位，不稳定 ] O(n^2)
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52//冒泡排序
const bubbleSort=(arr)=>{
let [temp,n]=[0,arr.length];
for(let i=0;i<n-1;i++){
for(let j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1]){
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
console.log(bubbleSort([2,5,6,1,3,0,4]));
//冒泡排序---> 优化,加一个标记didSwap，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。
const bubbleSort1=(arr)=>{
let [temp,n,didSwap]=[0,arr.length,false];
for(let i=0;i<n-1;i++){
for(let j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1]){
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
didSwap=true
}
}
if(didSwap===false){
return;
}
}
return arr;
}
//选择排序
const selectSort=(arr)=>{
let n=arr.length,min;
for(let i=0;i<n-1;i++){
min=i;
for(let j=i+1;j<n;j++){
if(arr[j]<arr[min]){
min=j;
}
}
let temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
return arr;
}
console.log(selectSort([1,6,7,2,3,9,3]));
减治法
- 插入排序：类似于扑克牌摸牌整牌。 [ 在位，稳定 ] 最好是O(n) 最差是O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14const insertSort=(arr)=>{
let [index,item,n]=[0,0,arr.length];
for(let i=1;i<n;i++){
index=i-1;
item=arr[i];
while(index>=0 && arr[index]>item){
arr[index+1]=arr[index];
index--;
}
arr[index+1]=item;
}
return arr;
}
console.log(insertSort([3,1,2,5,4,7,1,3,5]));
分治法
主定理：最早出现在《算法导论》中，提供了分治方法带来的递归表达式的渐近复杂度分析。
规模为n的问题通过分治，得到a个规模为n/b的问题，每次递归带来的额外计算为c(n^d)
T(n) <= aT(n/b)+c(n^d)
那么就可以得到问题的复杂度为：- T(n) = O(n^d log(n)), if a = b^d
- T(n) = O(n^d ), if a < b^d
- T(n) = O(n^logb(a))), if a > b^d
快排：包含三个方面，将整体分成为2个n/2规模的子问题，同时再调用partition合并，partition效率为N
- 归并排序 [ 不在位，稳定 ] O (n log n)
- 快速排序 [ 在位，不稳定 ] 最好 O(nlog n) 最坏 O(n^2)
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70//归并排序
const merge=(arr,l,r,m)=>{
let [i,j,k,helpArr]=[l,m+1,l,[]];
while( i<=m && j<=r){
if(arr[i]<=arr[j]){
helpArr[k++]=arr[i++];
}
else{
helpArr[k++]=arr[j++];
}
}
while(i<=m){
helpArr[k++]=arr[i++];
}
while(j<=r){
helpArr[k++]=arr[j++];
}
for(let i=l;i<=r;i++){
arr[i]=helpArr[i];
}
return arr;
}
const mergeSort=(arr,l,r)=>{
let mid;
if(l<r){
mid=Math.floor((l+r)/2);
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,r,mid);
}
return arr;
}
console.log(mergeSort([3,1,2,5,4,7,1,3,5],0,8));
//快速排序
const swap=(arr,i,j)=>{
let temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
return arr;
}
const partition=(arr, l, r) => {
// v是哨兵
var v = arr[l];
// j是分界线
var j = l;
//从第二个元素开始比较
for (var i = l + 1; i <= r; i++) {
if (arr[i] < v) {
//如果第i个元素比哨兵小，就和右边的大数交换，j就往右移了一位
[arr[j + 1], arr[i]] = [arr[i], arr[j + 1]];
j++;
}
}
//把哨兵放在本应属于他的位置。
[arr[l], arr[j]] = [arr[j], arr[l]];
return j;
}
const quickSort=(arr,l,r)=>{
if(r>=arr.length){
throw new Error('Incorrect input!');
}
if(l<r){
s=partition(arr,l,r);
quickSort(arr,l,s-1);
quickSort(arr,s+1,r);
}
return arr;
}
console.log(quickSort([4,3,7,9,0,2,3,1,5],0,8));变治法
- 堆排序
- 构造堆（堆—–>父母优势，完全二叉树）
- 删除最大键（根的键和堆的最后一个键K做交换，堆的规模减一，堆化）
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
36
37
38
39const maxHeapify=(H,i,n)=>{
let largest=i;//用于标记最大的元素
if(2*i<=n && H[i]<H[2*i]){
largest=2*i;
}
if(2*i+1<=n && H[largest]<H[2*i+1]){//这里是largest不是i
largest=2*i+1;
}
if(largest!=i){
let temp=H[i];
H[i]=H[largest];
H[largest]=temp;
maxHeapify(H,largest,n);//交换以后，可能下面的元素不满足父母优势了
}
}
//自底向上构造堆,传入一个数组和数组的大小
const heapBottomUp=(H,n)=>{
H.unshift(null);//占位数组的第一个元素
for(let i=Math.floor(n/2);i>=1;i--){//从最后一个父母节点开始构造
maxHeapify(H,i,n);//最大堆化
}
H.shift();
return H;
}
const heapSort=(H)=>{
let len=H.length;
heapBottomUp(H,len);//构造堆
for(let i=len-1;i>0;i--){
//交换最大键和最后一个键
let temp=H[i];
H[i]=H[0];
H[0]=temp;
//构造堆(除去最后一个元素后的堆化)
heapBottomUp(H,i);
}
return H;
}
console.log(heapSort([9,0,1,6,7,3,4,5,6,3,2]));- 堆排序
栈、队列、链表
栈的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Stack{
constructor(){
this.stack=[];
}
push(item){//入栈
this.stack.push(item);
}
pop(){//出栈
this.stack.pop();
}
peek(){//获取栈顶元素
return this.stack[this.getLength()-1];
}
getLength(){//获取长度
return this.stack.length;
}
isEmpty(){//判断是否为空
return this.getLength()===0;
}
}队列的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Queue{
constructor(){
this.queue=[];
}
enQueue(item){//入队
this.queue.push(item);
}
deQueue(){//出队
return this.queue.shift();//shift() 移除数组的第一项，返回移除项
}
getHeader(){//获取队首元素
return this.queue[0];
}
getLength(){//获取长度
return this.queue.length;
}
isEmpty(){//判断是否为空
return this.getLength()===0;
}
}链表的实现
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64class LNode{//链表结点
constructor(elem,next){
this.elem=elem;//数据域
this.next=next;//指针域
}
}
class LinkedList{//链表
constructor(){
this.size=0;//链表长度
this.dummyHead=new LNode(null,null);//头结点
}
//检查下标
checkIndex(index){
if(index < 0 || index > this.size) throw Error('Index Error');
}
//查找元素节点
find(head,curIndex,searchIndex){
if(searchIndex===curIndex) return head;
return this.find(head.next,curIndex+1,searchIndex);
}
//添加元素
addNode(ele,index){
this.checkIndex(index);
//s->next=p->next p->next=s
let prev=this.find(this.dummyHead,0,index);
prev.next=new LNode(ele,prev.next);
this.size++;
return prev.next;//返回添加的元素
}
//任意插入元素
insertNode(ele,index){
return this.addNode(ele,index);
}
//删除元素
removeNode(index,isLast){
this.checkIndex(index);
let prev=this.find(this.dummyHead,0,index-1);
let removeNode=prev.next;//要删除的元素
prev.next=removeNode.next;
removeNode.next=isLast?removeNode.next:null;
this.size--;
return removeNode;
}
//获取元素
getNode(index){
this.checkIndex(index);
if(this.isEmpty()) return;
return this.find(this.dummyHead,0,index);
}
isEmpty(){
return this.size===0;
}
getSize(){
return this.size;
}
}
let list=new LinkedList(0);
list.addNode(1,0);
list.addNode(2,1);
list.addNode(3,2);
console.log(list.removeNode(3,true));
console.log(list.getNode(1));
树的深度优先遍历和广度优先遍历
- DFS
1 | const deepTraversal=(node) => { |
- BFS
1 | const wideTraversal=(node)=>{ |
- 特殊的深度遍历——前序遍历
1 | const preOrderTraversal=(root) => { |
- 特殊的深度遍历——中序遍历
1 | const inOrderTraversal=(root) => { |
- 特殊的深度遍历——后序遍历
1 | const postOrderTraversal=(root) => { |
二分搜索
二分搜索树
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
36
37
38
39
40class Node{
constructor(val){
this.value=val;
this.left=null;
this.right=null;
}
}
class BST{
constructor(){
this.root=null;
this.size=0;
}
getSize(){
return this.size;
}
isEmpty(){
return this.size===0;
}
addNode(val){
this.root=this._addChild(this.root,val);
}
_addChild(node,val){
if(!node){
this.size++;
return new Node(val);
}
if(node.value>val){
node.left=this._addChild(node.left,val);
}else if(node.value<val){
node.right=this._addChild(node.right,val);
}
return node;
}
}
let bsTree=new BST();
bsTree.addNode(5);
bsTree.addNode(2);
bsTree.addNode(6);
console.log(bsTree);二分搜索
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//递归版
function recursionBS(arr,l,r,k){//arr是排好序的数组
if(r-l<0){
return -1;//没有元素
}
let mid=Math.floor((l+r)/2);
if(k===arr[mid]) return mid;
else if(k<arr[mid]) return BS(arr,l,mid-1,k);
else return BS(arr,mid+1,r,k);
}
console.log(recursionBS([1,2,3,4,5,6],0,5,3));
//迭代版
function iterationBS(arr,l,r,k){
if(r-l<0){
return -1;//没有元素
}
let mid;
while(l<=r){
mid=Math.floor((l+r)/2);
if(k===arr[mid]) return mid;
else if(k<arr[mid]) r=mid-1;
else l=mid+1;
}
}
console.log(iterationBS([1,2,3,4,5,6],0,5,3));
动态规划
核心： 记住已经解决过的子问题的解。用空间换时间。
原理
最优子结构：选或不选 ，是两种情况， 同时诞生了两个子问题。求解这两个子问题 然后比较结果 填入最优的那一个。
重叠子问题：在斐波拉契数列中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次。
贪心算法
- 满足条件
- 1、可行的：即它必须满足问题的约束。
- 2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
- 3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。
- 贪心在解决问题上是目光短浅的，仅仅根据当前的已知信息就做出选择，并且一旦做了选择，就不再更改比如01背包问题，用贪心的话是不可解决的，因为贪心每次只顾眼前最优，即每次选择价值最大的，而忽略了另外一个变量，物品的重量，如果还考虑物品的重量的话，那就是dp了