数据结构和算法真的不难
原创
先从数组和链表说起
数组
是一个连续的单元格子存储在内存中的一组数据，元素内存在很多编程语言中是要求相同的，比如Java，c，但是对于一些脚本语言却是不那么回事，比如JavaScript，就允许数组中每个元素的类型各不相同，其特点是：查找某个位置的元素飞快，但是对短板也很明显，对于插入删除元素会存在大量的补位操作，较为耗时。
链表
是用链子[在C语言中是指针，但是后面发现其实说引用也可能更加通用一些]来串起来的，它不要求存储的数据在内存中是一连串的数据，因此他有一个特点，查找某个位置的元素比较耗时，因为你得挨个走过去，但是插入删除就显得很容易而又快捷了。
对于以上两个数据结构，其共同的特点是线性的，适用的场景通常是存储一组有顺序的数据，然后一个共同的特性，他们具备可以被递归的特性，因为少一个节点，他还是他。理解这点很重要，算法上很多优雅的方式都是适用递归解决的。
在说几种排序算法
冒泡排序
简单，就是一个数组中，做两层嵌套循环，前后两个数两两比较，没一个大轮循环就会把本轮最大的冒到最后，当然你反着来把最小的浮动到最前面一点问题都每有，其特点是，时间复杂度巨差，O(N^2)，一般来说，就没有任何的使用场景 ，一般是不会用它的，因为他太戳啦....
插入排序
插入排序就是从数组的2个位置开始，也就是下标为1的地方（注意，在计算机学科中第0个位置是人们通常认为的第一个，数组第1个其实时第二个原生了），把他拧出来，然后左边的元素逐个和他比较，直到找到一个表小的或者碰到了下标为0，就把刚才拧出来的家伙插入进入，这就是插入排序。同样时间复杂度是O(N^2)，但是较多地方还是采用这个排序，因为他其实是[N^2/ 2]，而冒泡排序可是扎扎实实的[N^2]
选择排序
选择排序就更加好说了，就是每轮去找到最小元素的位置，把他放到本轮的开始位置，同样的道理时间复杂度是O(N^2)，但是人家站到冒泡排序面前，冒泡也得喊一声大哥不是，因为人家移动的元素的次数少了很多，这就是优势所在。
经过上面三个排序，我们发现，虽然同样是O(N^2)的时间复杂度，但是，总结在数据量大的时候，有些优势就体现出来了，这就好比同样是斗皇强者，也是有星级区别的。
归并排序
这个就牵扯到了递归，我们要对一个数据排序，那么，可以把数组切割为两个数组来进行这样的排序，切割到不能切割为止，没错，你可以脑补为只有一个元素的数组，然后就是合并，这个合并就是有序的数组合并了。
function merge(arr1:number[], arr2:number[]) {
return [];
}
function mergeSort(arr:number[]):number[] {
if (arr.length < 2) {
return arr;
}
const mid = arr.length >> 1;
const left = arr.slice(0, mid);
const right = arr.slice(mid);
console.log(left, 'vs', right);
return merge(mergeSort(left), mergeSort(right));
}
mergeSort([11, 9, 7, 1, 5, 4, 3, 8]);
------------------------------
[ 11, 9, 7, 1 ] vs [ 5, 4, 3, 8 ]
[ 11, 9 ] vs [ 7, 1 ]
[ 11 ] vs [ 9 ]
[ 7 ] vs [ 1 ]
[ 5, 4 ] vs [ 3, 8 ]
[ 5 ] vs [ 4 ]
[ 3 ] vs [ 8 ]
因为，这个算法比较有意思，所以我写一下大概的框架，然后把每次划分的过程给打印了出来，这样就比较好理解递归的过程啦，merge两个有序的部分我就不写了，这个不是算法的精华部分，这个算法的时间复杂度Nlog(N)) 。不过这个是平均的，是不是秒杀了上面三个大多数场景了。
快速排序
这个就更加有意思了，思想就是，选取一个基数，你也可以叫做靶点，通常就是数组的第一个元素或者最后一个，都行，然后就是在数组剩余的部分首尾各放一个指针；
1、左边指针往右边移动，直到找到一个比基数大的；
2、右边指针往左移动，直到找到一个比基数小的；
3、然后交换两个指针所指的数据；
1、2、3这三个步骤如果发生左边的指针遇到右边的指针的情况，就停止1、2、3，然后把技术和左指针指的位置换一下就好。
然后基数两侧就分成了两段可以执行快速排序的单元了。
function quickSort(arr:number[], left:number, right:number) {
if (left >= right) {
return;
}
let start = left; let end = right;
const base = arr[end];
end = end - 1;
while (start < end) {
while (arr[start] <= base && start < end) {
start = start + 1;
}
while (arr[end] > base && start < end) {
end = end - 1;
}
swap(arr, start, end);
}
swap(arr, start, right);
//这里通过base隔开两段继续递归搞起
quickSort(arr, left, start - 1);
quickSort(arr, start + 1, right);
}说下栈和队列
栈和队列是一个非常神奇的数据接口，可以说我们的程序指令的执行离不开这哥俩，我们知道一个函数的执行需要把这个函数压到执行栈中去，等这个函数执行完之后，又需要把这个函数弹出栈来，他是一个不用关心元素顺序，但是冥冥之中又为你设定好了顺序的结构，他具备先进后出的特性，而队列的话，是先进先出，基于他们俩的这个特性，我们关心的是栈和队列使用与那些场景；
栈
适用于做递归
适用于做回溯，比如走迷宫，去探路，遇到思路不行赶紧回退
适用于函数的执行
适用于去做一个有来又回的匹配工作，比如检查一个表达式是否括号匹配
const map = {
'}': '{',
')': '(',
']': '[',
};
function checkBrackets(str:String):boolean {
const items = str.split('');
const stack = [];
let index = 0;
stack.push(items[index]);
while (index < items.length) {
index = index + 1;
const currentItem = items[index];
// 如果不是括号之类的直接过滤
if (!(['{', '}', '[', ']', '(', ')'].includes(currentItem))) {
continue;
}
// 如果栈是空且还没比对完，进直接入栈
if (stack.length === 0) {
stack.push(currentItem);
continue;
}
const currentTop = stack.pop();
if (map[currentItem] === currentTop) {
continue;
} else {//不匹配，把两个都放回去
stack.push(currentTop);
stack.push(currentItem);
}
}
return stack.length === 0;
}
console.log(checkBrackets('[{1}{[2+12]}{[]}]'));
console.log(checkBrackets('{1}{[2{12]}{}'));
队列
适用于去管理任务，比如，我们非常有名的消息队列
做树的广度优先便利，这个在说道树的时候会给一个例子。
总结一下，栈和队对比与数组和链表具备一个特性是，他是弹性的。
说下树
树这个数据结构在查找中使用得比较多的，关键是比较形象，如一颗二叉树，就特别适合做二分查找，二分查找的相率可是杠杠的，O(LOG(N))，指数级收敛的速度，是在是很恐怖。但问题的前提是你的数需要是一颗这样的二叉树；
二叉树
满足左边子树的节点值都要比右边子树小。树这个数据结构就特别适合使用递归的方式去解决问题。
/**
* 先根遍历
* @param tree 二叉树
*/
function PreOrderVisitor(tree: BTreeNode) {
if (tree === null) return;
console.log(tree.value);
if (tree.left !== null) {
PreOrderVisitor(tree.left);
}
if (tree.right !== null) {
PreOrderVisitor(tree.right);
}
}vs
/**
* 中序遍历
* @param tree 二叉树
*/
function MidOrderVisitor(tree: BTreeNode) {
if (tree === null) return;
if (tree.left !== null) {
MidOrderVisitor(tree.left);
}
console.log(tree.value);
if (tree.right !== null) {
MidOrderVisitor(tree.right);
}
}普通树
普通树就是说，一个根节点上可能不止一个孩子啦，这种书通常情况下使用的不是太多，还记得前面我输过要使用队列给你做一个广度优先遍历下树吗？
/**
* 广度优先遍历树
* @param tree 树
*/
function bfsTravel(tree:TreeNode) {
if (tree === null) return;
const root = tree;
// root.visited = true;
const queen = [];
queen.push(root);
while (queen.length > 0) {
const current = queen.shift();
console.log(current.value);
visit(current, queen);
}
}
function visit(tree:TreeNode, queen):void {
for (let i = 0;i < tree.children.length ;i++) {
const current = tree.children[i];
// current.visited = true;
queen.push(current);
}
}最后想说下递归
递归实在是太重要了，可以说在我们编码的过程中，递归能解决大多数的问题，而且解决问题的方式让人很容易理解，只要你把问题描述清楚了，你就解决了问题；比如经典的汉诺塔的问题，如果让你使用非递归的方式去解决这个问题，恐怕你想到疯都想不到如何解决这个问题，但是如果你使用递归的方式去解，那就很好理解了；
function hanota(n, a, b, c) {
if (n === 1) {
console.log(`${a}->${c}`);
} else {
hanota(n - 1, a, c, b); //先把 N-1 个盘子从a移动到b，辅助盘子是c
console.log(`${a}->${c}`); //把 a 上的 盘子移动到 c 上
hanota(n - 1, b, a, c); // 最后在把 b 的 N-1 个盘子移动到 c 上，辅助盘子是 a
}
}
hanota(5, 'a', 'b', 'c');//把5个盘子从a移动到c，辅助使用b
写到最后，没中数据结构都有他使用的场景，算法是要依赖数据结构的，当你在遇到一个问题时，首先，你应该想到的是这个问题使用什么样的数据结构来表达，其次在来看这个问题是否可以通过规模简化为子问题，也就是说往递归上靠，用计算机能懂的语言把问题描述清楚，那么这个问题基本上就解了。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。