算法
排序算法
选择排序
- 双层循环(i 从 0 到 length - 1, j 从 i + 1 到 length - 1)
- 比较 list[i] 与 list[j] 大小,如果 list[j] < list[i] ,则交换位置
时间复杂度: $O(N^2)$
归并排序
- 等分目标,直到等分的结果长度为1(时间复杂度 $O(log_2 N)$)
- 开始循环,每次 + 2 ,单词循环中对比相邻的两项进行排列,合并之后得到长度为2的单元
- 同上次循环,合并得到长度为4的单元
- …
- 直到最后,完成合并,得到正确排序数组
时间复杂度: $O(N log_2 N)$
图搜索算法:地图常用,比如获取从一个地方到另外一个地方最近的路线
最普通的 Dijkstra 算法: O(N^2)
优化后: O(N * logN)
数据结构
数组,在内存上顺序存储。字符串是一种在内存上尾部指针指向 “null” 的数组(即在内存上最后一位是二进制0)。因为是顺序存储,所以很难插入修改。数组中的节点可以一个结构体,这样便可以方便修改。下面是几种常见的结构体数组:
链表
每个元素叫做 Node, 存储了一个变量和一个指针(在内存上占用了两个位置),这个指针指向了下一个节点。通过新增一个节点,修改指针的指向可以方便的插入。
链表有两个比较出名的个例:队列、栈。他们的区别是先进先出与后进先出,专有名词有:出队、进队、出栈、进栈
树
它的节点存储了一个变量和两个指针(在内存上占用了三个位置),分别是左指针和右指针。
专有名词有: 根节点、母节点、子节点、叶节点(没有子节点的节点)
图
它的节点存储了一个变量和多个指针