DS
Data structure 数据结构
概述
线性表
链表和数组的区别：数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组利用下标定位，链表遍历；数组插入或者删除时间复杂度o(n)，而链表o(1)；数组元素在栈区，链表元素在堆区。
堆和栈的区别：
栈和队列
区别：队列限定了只能在表的一端进行插入和在另一端进行删除，表头删除，表尾插入，队列先进先出，队列通常应用在计算机系统中各种资源的管理，队列的遍历速度更快，基于地址指针进行遍历，从头部到尾部进行遍历，无需开辟空间；而栈是限定只能在表的一端进行插入和删除，先进后出，删除和插入都在表尾，通常应用在括号求解。
两个队列实现一个栈，队列1作为进出栈，队列2作为中转，入栈时，直接压入队列1，出栈时，先将队列1中元素除最后一个外依次出队列，压入队列2，然后将队列1中的最后一个元素出队即出栈，最后再把队列2中的元素压入队列1.
两个栈实现一个队列，设定栈1是入栈，栈2是出栈，入队的时候直接压入栈1，出队的时候，先看栈2是否为空，如果不为空，把栈2栈顶元素弹出；为空就把栈1所有元素压入栈2，再弹出栈顶元素。
串
树和二叉树
二叉树遍历：中序LNR，前序NLR，后序LRN，
图
查找
处理冲突的方法
字符串KMP匹配
排序
八大排序
冒泡排序
重复走访要排序的数列，一次比较两个元素，如果顺序错误就交换。走访数列重复到没有再需要交换。越小的元素会由交换慢慢“浮”到数列顶端。
平均、最坏：O(n^2)。最好：O(n)
O(1)
稳定
快速排序
在序列中选出一个元素作为基准，把所有比他小的放前面，比他大的放后面，再对分区递归进行这些操作。
平均、最好：O(nlog_2 n), 最坏：O(n^2)
O(nlog_2 n)
不稳定
希尔排序
平均：O(n^{1.3})，最好：O(n), 最坏：O(n^2)
O(1)
不稳定
二分插入排序
平均、最坏：O(n^2)。最好：O(nlog_2 n)
O(1)
稳定
直接插入排序
平均、最坏：O(n^2)。最好：O(n)
O(1)
稳定
堆排序
平均、最坏、最好：O(nlog_2 n)
O(1)
不稳定
选择排序
平均、最坏、最好：O(n^2)
O(1)
不稳定
归并排序
平均、最坏、最好：O(nlog_2 n)
O(n)
稳定
Linux系统管理
Last updated