数据结构
老李 Lv4
  2019-08-19 09:24:21 2019-08-19 09:24   2023-07-11 02:03:44    

定义

是相互之间存在一种或多种特定关系的数据元素的集合。

数据之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构”
结构=关系+实体

另一种定义：按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合。

数据结构基础类型

四种基本逻辑结构

  • 集合：元素仅属于同一个集体，没有其他关系。
  • 线性结构：存在一对一 关系，序列相邻，次序关系。
  • 树型结构：存在一对多关系，层次关系。
  • 图状结构（网状结构） ：存在多对多关系，任意性

数组

数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)。

链表

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是O(1)。

栈

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则（FILO）。

队列

队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则（FIFO）。

散列表

散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。

在 java 中 ThreadLocalMap 解决哈希冲突使用的是开放寻址法，HashMap 解决哈希冲突使用的是链表法。

二叉树

二叉树：二叉树是有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。

二叉树的性质：

  • 性质1：在二叉树中第 i 层的结点数最多为 2^(i-1) (i ≥ 1)
  • 性质2：高度为k的二叉树其结点总数最多为 2^k-1 (k ≥ 1)
  • 性质3：对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1
  • 性质4：具有 n 个结点的完全二叉树的深度为 log2n + 1

满二叉树（完美二叉树）：深度为k且有 2^k - 1 个结点的二叉树称为满二叉树

完全二叉树：深度为 k 的，有N个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，称之为完全二叉树。（除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点）

完满二叉树：所有非叶子结点的度都是2

排序算法

插入排序

直接插入排序

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
要点：设立哨兵，作为临时存储和判断数组边界之用。

希尔排序

原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。
要点：增量的选择以及排序最终以1为增量进行排序结束。

交换排序

冒泡排序

原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。
要点：设计交换判断条件，提前结束以排好序的序列循环。

快速排序

原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。
要点：递归、分治。

选择排序

直接选择排序

原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。

堆排序

原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。
要点：建堆、交换、调整堆

归并排序

归并排序

原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。
要点：归并、分治

基数排序

基数排序

原理：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。
要点：对关键字的选取，元素分配收集。

排序算法效率

稳定排序

  • 冒泡排序（Bubble Sort） — O(n²)
  • 插入排序（Insertion Sort）— O(n²)
  • 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
  • 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
  • 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
  • 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
  • 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间

不稳定排序

  • 选择排序（Selection Sort）— O(n²)
  • 希尔排序（Shell Sort）— O(nlogn)
  • 堆排序（Heapsort）— O(nlogn)
  • 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序