数据结构与算法的关系算法和架构有什么区别( 三 ) _经验知识

什么是链表？链表是一种链式数据结构。由若干节点组成。每个节点包含指向下一节点的指针。链表的物理存放方式是随机存放。访问方式是顺序访问。查找链表节点的期间复杂度是O(n) 。中间插入、删除节点的期间复杂度是O(1) 。
什么是栈？栈是一种线性逻辑结构。可以用数组实现。也完全可以用链表实现。栈包含入栈和出栈操作。遵循先入后出的原则（FILO）。
什么是队列？队列也是一种线性逻辑结构。可以用数组实现。也完全可以用链表实现。队列包含入队和出队操作。遵循先入先出的原则（FIFO）。
什么是散列表？散列表也叫哈希表。是存放Key-Value映射的集合。对于某一个Key 。散列表可以在接近O(1)的期间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换。通过开放寻址法和链表法来解决哈希冲突。
什么是树？树是n个节点的有限集。有且仅有一个特定的称为根的节点。当n>1时。其余节点可分为m个互不相交的有限集。每一个集合本身又是一个树。并称为根的子树。
什么是二叉树？二叉树是树的一种特殊形式。每一个节点最多有两个儿童节点。二叉树包含完全二叉树和满二叉树两种特殊形式。
二叉树的遍历方式有几种？根据遍历节点之间的关系。可以分为前序遍历、中序遍历、后序遍历、层序遍历这4种方式；从更宏观的角度划分。可以划分为深度优先遍历和广度优先遍历两大类。
什么是二叉堆？二叉堆是一种特殊的完全二叉树。分为最大堆和最小堆。在最大堆中。任何一个父节点的值。都大于或等于它左、右儿童节点的值。在最小堆中。任何一个父节点的值。都小于或等于它左、右儿童节点的值。
什么是优先队列？优先队列分为最大优先队列和最小优先队列。
在最大优先队列中。无论入队顺序如何。目前最大的元素都会优先出队。这是基于最大堆实现的。
在最小优先队列中。无论入队顺序如何。目前最小的元素都会优先出队。这是基于最小堆实现的。
04 排序算法4.1 冒泡排序冒泡排序的英文是bubble sort 。它是一种基本的交换排序。

文章插图
遵从冒泡排序的思想。咱们要把相邻的元素两两比较。当一个元素大于右侧相邻元素时。交换它们的位置；当一个元素小于或等于右侧相邻元素时。位置不变。
排序过程如下

文章插图

文章插图
到此为止。所有元素都是有序的了。这就是冒泡排序的全体思路。冒泡排序是一种稳定排序。值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素。总共遍历（元素数量-1）轮。所以平均期间复杂度是O(n2) 。
4.2 超快排序同冒泡排序一样。超快排序也属于交换排序。通过元素之间的比较和交换位置来达到排序的目的。不同的是。冒泡排序在每一轮中只把1个元素冒泡到数列的一端。而超快排序则在每一轮选择一个基准元素。并让其他比它大的元素移动到数列一边。比它小的元素移动到数列的另一边。从而把数列拆解成两个部分。

文章插图

文章插图
在分治法的思想下。原数列在每一轮都被拆分成两部分。每一部分在下一轮又分别被拆分成两部分。直到不可再分为止。每一轮的比较和交换。需要把数组全部元素都遍历一遍。期间复杂度是O(n) 。这样的遍历一共需要多少轮呢？假如元素个数是n 。那么平均情况下需要logn轮。因此超快排序算法总体的平均期间复杂度是O(nlogn) 。
4.3 堆排序堆排序算法的步骤。
把无序数组构建成二叉堆。循环删除堆顶元素。并将该元素移到集合最底部。调整堆产生新的堆顶。第1步。把无序数组构建成二叉堆。这一步的期间复杂度是O(n) 。第2步。需要进行n-1次循环。每次循环调用一次downAdjust方法。所以第2步的计算规模是 (n-1)×logn。期间复杂度为O(nlogn) 。两个操作教程步骤是并列关系。所以全体的期间复杂度是O(nlogn) 。