盒子
盒子
文章目录
  1. 常见的数据结构
  2. 树的遍历
  3. 树节点的插入和删除
  4. 插入排序
  5. 选择排序
  6. 冒泡排序
  7. 快速排序
  8. 归并排序

数据结构与算法

常见的数据结构

  • 线性表

    链表是一个线性结构,同时也是一个天然的递归结构,链表增加了节点的指针域,空间开销比较大。

    循环单链表是链表的最后一个节点指向第一个节点,构成一个链环。

    双向链表是节点中包含两个指针部分,一个指向前驱元,一个指向后继元。

  • 栈和队列

    栈是一个线性结构,只能在某一端添加或删除数据,遵循先进后出的原则。对栈的基本操作有进栈(push)(pop)出栈,相当于插入和删除最后一个元素。可以用数组实现。

    队列是一种特殊的线性表,只允许在表的前端(front)进行删除操作,在表的后端(rear)进行插入操作。

  • 树与二叉树

    • 树,是由n个有限节点组成一个具有层次关系的集合,是一种非常重要的数据结构。每个节点有零个或多个子节点,没有父节点的节点称为根节点;每个非根节点有且只有一个父节点;没有子节点的节点称为叶子结点;除了根节点外,每个子节点都可以分为多个不相交的子树。
    • 二叉树,是每个节点最多拥有两个子节点,分别为左节点和右节点
    • 二叉查找树,也叫二叉排序树,二叉搜索树。与二叉树的区别在于每个节点的值都比他的左子树大,比右子树小
  • 图,是一种比树更为复杂的数据结构。树的节点之间是一对多的关系,且存在父子的层级划分;图的顶点之间是多对多的关系,并且所有的节点都是平等的,没有谁是父谁是子。

树的遍历

树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历

先序遍历算法:先访问根节点,然后访问左节点,最后访问右节点。

1
2
3
4
5
6
7
8
9
10
preTraversal() {
this._pre(this.root)
}
_pre(node) {
if(node) {
console.log(node.value)
this._pre(node.left)
this._pre(node.right)
}
}

中序遍历算法:先访问左节点,然后访问根节点,最后访问右节点。

1
2
3
4
5
6
7
8
9
10
11
midTraversal() {
this._mid(this.root)
}

_mid(node) {
if(node) {
this._mid(node.left)
console.(node.value)
this._mid(node.right)
}
}

后序遍历算法:先访问左节点,然后访问右节点,最后访问根节点。

1
2
3
4
5
6
7
8
9
10
backIraversal() {
this._back(this.root)
}
_bcak(node) {
if(node) {
this._back(node.left)
this._back(node.right)
console.log(node.value)
}
}

层次遍历,使用队列结构完成。

1
2
3
4
5
6
7
8
9
10
breadthTraversal() {
if(!this.root) return null
let q = new Queue()
q.enQueue(this.root)
while (!q.isEmpty()) {
let n = q.deQueue()
if(n.left) q.enQueue(n.left)
if(n.right) q.enQueue(n.right)
}
}

树节点的插入和删除

  • 节点插入

    将该节点的值与树上节点的值做比较,如果小于,继续遍历左子树;如果大于,继续遍历右子树。如果左右子树为空,那么直接插入。如果大于左子树,则判断右子树;如果小于右子树,则判断左子树。

  • 节点删除,节点删除分为三种情况

    • 需要删除的节点没有子树
    • 需要删除的节点只有一条子树
    • 需要删除的节点有左右两条树

    最复杂的是第三种情况,解决办法为:找到需要删除节点p的直接前缀p(或直接后缀)s,用s来替换节点p,然后再删除此节点s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
delect(v) {
this.root = this._delect(this.root, v)
}
_delect(node, v){
if(!node) return null
// 判断在左子树还是在右子树
if(node.value < v) {
node.right = this._delect(node.right.v)
} eles if(node.value > v) {
node.left = this._delect(node.left.v)
} else {
if (!node.left) return node.right
if (!node.right) return node.left
// _getMin()获取右树上最小的节点 _delectMin()删除最小节点
//
let min = this._getMin(node.right)
min.right = this._delectMin(node.right)
min.left = node.left
node = min
}
// 维护size
node.size = this._getSize(node.left) + this._getSize(node.right) + 1
return node
}

插入排序

构建有序序列,扫描已排序序列,将数据插入到有序序列中合适的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function checkArray(array) {
return Array.isArray(array)
}

function swaps(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}

function insertion(array) {
if (!checkArray(array)) return
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
swap(array, j, j +1)
}
return array;
}

选择排序

在序列中找出最小的元素,放到排序序列的起始位置,然后再从剩下的序列中再找出最小的元素,重复这个过程。

1
2
3
4
5
6
7
8
9
10
11
function select(array) {
if (!checkArray(array)) return
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for(let j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
swap(array, i, minIndex);
}
return array;
}

冒泡排序

比较两个元素,将较大的元素放在后边,当一次循环完成后,最大的元素被放在最后的位置,循环这个过程,知道排序完成。

代码实现:

1
2
3
4
5
6
7
8
funciton bubble(array) {
checkArray(array);
for (let i = array.legth - 1; i > 0; i--){
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) swap(array, j, j+1)
}
}
}

快速排序

在序列中选取一个值,将比该值小的元素放在左边,比该值大的放在右边,在分别对左右两侧的元素做相同的操作,直到排序完成。

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
function sort(array) {
if (!checkArray(array)) return
quickSort(array, 0, array.length - 1);
return array;
}

function quickSort(array, left, right) {
if (left < right) {
swap(array, , right)
// 随机取值,然后和末尾交换,这样做比固定取一个位置的复杂度略低
let indexs = part(array, parseInt(Math.random() * (right - left + 1)) + left, right);
quickSort(array, left, indexs[0]);
quickSort(array, indexs[1] + 1, right);
}
}
function part(array, left, right) {
let less = left - 1;
let more = right;
while (left < more) {
if (array[left] < array[right]) {
// 当前值比基准值小,`less` 和 `left` 都加一
++less;
++left;
} else if (array[left] > array[right]) {
// 当前值比基准值大,将当前值和右边的值交换
// 并且不改变 `left`,因为当前换过来的值还没有判断过大小
swap(array, --more, left);
} else {
// 和基准值相同,只移动下标
left++;
}
}
// 将基准值和比基准值大的第一个值交换位置
// 这样数组就变成 `[比基准值小, 基准值, 比基准值大]`
swap(array, right, more);
return [less, more];
}

归并排序

将序列的元素分成多个具有两个元素的子序列,将子序列排序后再将两个子序列合并,再排序再合并,直到合并为一个数组。

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
function sort(array) {
if (!checkArray(array)) return
mergeSort(array, 0, array.length - 1);
return array;
}

function mergeSort(array, left, right) {
// 左右索引相同说明已经只有一个数
if (left === right) return;
// 等同于 `left + (right - left) / 2`
// 相比 `(left + right) / 2` 来说更加安全,不会溢出
// 使用位运算是因为位运算比四则运算快
let mid = parseInt(left + ((right - left) >> 1));
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);

let help = [];
let i = 0;
let p1 = left;
let p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
help[i++] = array[p1++];
}
while (p2 <= right) {
help[i++] = array[p2++];
}
for (let i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
return array;
}
支持一下
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集