算法与数据结构

算法

排序算法

选择排序

  • 双层循环(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, 存储了一个变量和一个指针(在内存上占用了两个位置),这个指针指向了下一个节点。通过新增一个节点,修改指针的指向可以方便的插入。

链表有两个比较出名的个例:队列、栈。他们的区别是先进先出与后进先出,专有名词有:出队、进队、出栈、进栈

它的节点存储了一个变量和两个指针(在内存上占用了三个位置),分别是左指针和右指针。

专有名词有: 根节点、母节点、子节点、叶节点(没有子节点的节点)

它的节点存储了一个变量和多个指针

堂 wechat
欢迎关注我的微信公众号,里面有各种小故事哦!
坚持原创技术分享,您的支持将鼓励我继续创作!