算法
计算机知识思维导图：算法。网页展示前三层结构，可在线查看完整脑图并下载 GoMind 文件。
2026-08-25
## 算法 ### 算法 #### Untitled node #### Untitled node #### Untitled node #### O(1)<O(lgN)<O(N)<O(N*lgN)<O(n²)<O(n3)<O(2ⁿ) #### 递归 ##### 应用场景 ##### 实现 #### 排序算法 ##### 比较排序 ##### 非比较排序 #### 链表 ##### 链表逆序 #### 量级 ##### 2^20 约等于 100万，即百万个字节约等于1M ##### 2^30 约等于 10亿，即10亿个字节约等于1G #### 数据结构 ##### Skiplist ##### Tree ##### HashTable ##### 性能对比 > 仅展示前三层结构；请在线查看完整脑图或下载 GoMind 文件。
算法
算法
Untitled node
Untitled node
Untitled node
O(1)<O(lgN)<O(N)<O(N*lgN)<O(n²)<O(n3)<O(2ⁿ)
爬楼梯问题
母牛生仔问题
应用场景
时间复杂度为O(n)，空间复杂度为O(1)
function fibonacci(n){
var a,b,res;
a = b = 1;
if(n == 0){
return 0;
}
if(n == 1 || n == 2){
return 1;
}
for(var i=2;i<n;i++){
res = a + b;
a = b;
b = res;
}
return res;
}时间复杂度为O(n)，空间复杂度为O(n)
function fibo(x){
var arr = new Array(x);
arr[0] = 1;
arr[1] = 1;
for(var index=2;index<x;index++){
arr[index] = arr[index-1]+arr[index-2];
}
var result = 0;
arr.forEach((item)=>{
result+=item;
});
return result;
}
fibo(5);时间复杂度为 O(N*lgN)
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出实现
递归
冒泡排序 O(n²)
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}快速排序
每次取序列中的第一个数作为基准，将序列分为两部分，左边的数要小于基准值，右边的数大于基准值。具体做法是使用两个指针前后扫码序列，后面的指针先扫，若发现后面的值小于基准值则交换，接着前面的指针开始扫描，若前面的值大于基准值则交换。
巧妙之处在于partition方法中的置换
public static int partition(int[] arr,int start,int end){
int base = arr[start];
while(start<end){
while(arr[end]>base && start<end){
end--;
}
arr[start] = arr[end];
while(arr[start]<=base && start<end){
start++;
}
arr[end] = arr[start];
}
arr[start] = base;
return start;
}
public static void quickSort(int[] arr,int low,int high) {
if (low < high) {
int pivot = partition(arr, low, high); //将数组分为两部分
quickSort(arr, low, pivot - 1); //递归排序左子数组
quickSort(arr, pivot + 1, high); //递归排序右子数组
}
}交换排序
简单插入排序 O(n²)
从第一个元素开始，该元素可以认为已经排好序。取出下一个元素，在序列中从后向前扫描，如果该元素大于新元素，则将该元素移动到下一位。
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}希尔排序
插入排序
简单选择排序 O(n²)
没轮获取第一个数作为最大或最小值，再以该数与其他数字对比，对比后记录下最小或最大值的小标，每轮循环结束后将该下标与每轮中的第一个元素进行交换，依次循环直到结束
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}左边子节点为 2*n +1
右边子节点为 2*n + 2
父节点为 [n/2] （向下取整）
若节点下标为 n (n>1)
堆排序
堆排序就是利用堆得性质堆数组进行排序，待排序元素存放在一个数组Arr[0 ……n] 中，将Arr用一颗完全二叉树来表示，数组第一个元素就是完全二叉树的根，后面依次按层从左至右为，左孩子，右孩子，任意节点Arr[ i ] 的左孩子是Arr[ 2i+1 ]，右孩子是 Arr[ 2i+2 ] --------------------- 作者：askunix_hjh 来源：CSDN 原文：https://blog.csdn.net/m0_37925202/article/details/80818561 版权声明：本文为博主原创文章，转载请附上博文链接！
选择排序
二路归并排序
多路归并排序
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
比较排序
基数排序
计数排序
桶排序
非比较排序
排序算法
链表逆序
public class LinkedListReverse {
static class ListNode{
int data;
ListNode next;
public ListNode(int data){
this.data = data;
}
}
public static ListNode reverse(ListNode head){
if (head == null){
return null;
}
ListNode cur = head;
ListNode oldHead = null;
ListNode newHead = null;
while(cur != null){
oldHead = cur.next;
cur.next = newHead;
newHead = cur;
cur = oldHead;
}
return newHead;
}
public static void main(String[] args) {
// 测试
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
ListNode head = new ListNode(0);
head = reverse(node1);
System.out.print(head.data+" "+head.next.data+" "+head.next.next.data);
}
}
---------------------
作者：evillist
来源：CSDN
原文：https://blog.csdn.net/evillist/article/details/77124522
版权声明：本文为博主原创文章，转载请附上博文链接！链表
2^20 约等于 100万，即百万个字节约等于1M
2^30 约等于 10亿，即10亿个字节约等于1G
量级
Skiplist
AVL
AVL树是最早被发明的自平衡二叉查找树, 高度平衡树
RedBlackTree
B+Tree
Tree
HashTable
1. skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
2. 在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
3. 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
4. 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，
平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
5. 查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；
而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
6. 从算法实现难度上来比较，skiplist比平衡树要简单得多
性能对比
数据结构