数据结构知识

数据结构

数据结构知识

• 具体内容

  • 数组：数组的内存空间是连续的，随机访问的时间复杂度是O1，适用于需要按索引访问元素的场景，但是插入和删除元素较慢，时间复杂度是On
  • 链表：链表是由节点组成，节点之间是分散存储的，内存不连续，每个节点存储数据和指向下一个节点的指针。适用于频繁插入和删除元素的场景，随机访问元素较慢
  • 栈：栈是一种后进先出的数据结构，只允许在栈顶进行插入和删除操作
  • 队列：队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首删除元素
  • 树：树是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。树适用于表示层次关系的场景，例如文件系统、组织结构等

• 数组与链表区别？

  • 访问效率，插入和删除操作效率，缓存命中率
  • 应用场景：数组适合静态大小、频繁访问元素的场景，而链表适合动态大小、频繁插入、删除操作的场景

• 平衡二叉树

  • 二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
    1. 非空左子树的所有键值小于其根结点的键值。
    2. 非空右子树的所有键值大于其根结点的键值。
    3. 左、右子树都是二叉搜索树。
  • 二叉树搜索树的目的：缩短插入、删除、修改和查找节点的时间 一棵理想的二叉搜索树所有操作的时间可以缩短到 O(logn)
  • 一棵每个结点只有右孩子的二叉搜索树，那么性质就和链表一样
    • 平衡树将二叉查找树平衡均匀地分布，好处就是可以减少二叉查找树的深度
  • 平衡二叉树平衡的特性：
    • 左右两个子树的高度差（平衡因子）的绝对值不超过1
    • 左右两个子树都是一棵平衡二叉树

• 红黑树

  • 每个节点要么是红色，要么是黑色。
  • 根节点是黑色。
  • 每个叶子节点（NIL节点）是黑色。
  • 如果一个节点是红色，则其子节点必须是黑色。
  • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

• 二叉查找树

  • 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)
  • 平衡二叉查找树
    • 每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn)

• B+树

  • B+树是一种自平衡的多路查找树，所有叶节点都位于同一层，保证了树的平衡，使得搜索、插入和删除操作的时间复杂度为对数级别的
  • 非叶节点仅包含索引信息，不存储具体的数据记录，用来引导搜索到正确的叶节点
  • 所有数据记录都存储在叶节点中，且叶节点中的数据是按关键字排序的。叶节点包含实际的数据和关键字，是数据存储和检索的实体单元。叶节点之间通过指针相互链接，形成一个链表，便于范围查询和顺序遍历

• B+树与B-树

  • 检索路径：B树在查找数据时，可能在非叶子节点找到目标数据，路径长度不固定。B+树中所有数据都在叶子节点，查找数据时必须走到叶子节点，路径长度固定（均等）。即查找总是要到叶子节点结束
  • 叶子节点结构：B树中叶子节点之间没有特别的链接，彼此独立。B+树中叶子节点通过指针连接，形成一个有序链表，便于范围查询和顺序访问
  • 非叶子节点内容：B树中非叶子节点存储数据和索引。B+树中非叶子节点只存储索引，不存储实际数据。当数据量比较大时，相对于B树，B+树的层高更少，查找效率也就更高。
  • **高效地范围查询：**B+树叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树在进行范围查询时需要进行中序遍历，性能较差

• 堆

  • 堆是一颗完全二叉树，实现的堆也被称为二叉堆。堆中节点的值都大于等于（或小于等于）其子节点的值，堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于等于其子节点的值，我们将其称为小顶堆

排序算法

• 冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）。时间复杂度：最好情况下O(n)，最坏情况下O(n^2)，平均情况下O(n^2)。，空间复杂度：O(1)

  //冒泡排序
  public static void bubbleSort(int[] arr) {
      int temp;//临时变量
      boolean flag;//是否交换的标志
      for (int i = 0; i < arr.length - 1; i++) {   //表示趟数，一共 arr.length-1 次
          // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
          flag = false;
          for (int j = 0; j < arr.length - i - 1; j++) { //选出该趟排序的最大值往后移动
              if (arr[j] > arr[j + 1]) {
                  temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
                  flag = true;    //只要有发生了交换，flag就置为true
              }
          }
          //判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
          if (!flag) break;
      }
  }
  

• 插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。时间复杂度：最好情况下O(n)，最坏情况下O(n^2)，平均情况下O(n^2)，空间复杂度：O(1)。

• 选择排序（Selection Sort）：通过不断选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾（或开头）。时间复杂度：最好情况下O(n^2)，最坏情况下O(n^2)，平均情况下O(n^2)，空间复杂度：O(1)。

• 快速排序（Quick Sort）：通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于（或等于）基准元素，右子数组的元素都大于（或等于）基准元素，然后对子数组进行递归排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(n^2)，平均情况下O(nlogn)，空间复杂度：最好情况下O(logn)，最坏情况下O(n)

  //快速排序
  public static void quickSort(int[] arr, int low, int high) {
      //递归结束条件
      if (low >= high) {
          return;
      }
      //设定基准值
      int pivot = arr[high];
      //在[low,high]区间中将大于pivot的值放到右边，小于pivot的值放到左边
      int L = low, R = high;
      while (L < R) {
          //寻找比基准值pivot大的值的下标
          while (L < R && arr[L] <= pivot) {
              L++;
          }
          //此时L==R或者arr[L]>pivot,将arr[L]放到右边
          arr[R] = arr[L];
          //寻找比基准值pivot小的值的下标
          while (L < R && arr[R] >= pivot) {
              R--;
          }
          //此时L==R或者arr[R]<pivot,将arr[R]放到左边
          arr[L] = arr[R];
      }
      arr[L] = pivot;
      //对[low,L-1]区间进行排序
      quickSort(arr, low, L - 1);
      //对[L+1,high]区间进行排序
      quickSort(arr, L + 1, high);
  }
  

• 归并排序（Merge Sort）：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)。空间复杂度：O(n)

  //归并排序
  public static void mergeSort(int[] arr, int low, int high) {
      //递归结束条件
      if (low >= high) {
          return;
      }
      //将[low,high]区间分成两半
      int mid = (low + high) / 2;
      //对[low,mid]进行排序
      mergeSort(arr, low, mid);
      //对[mid+1,high]区间进行排序
      mergeSort(arr, mid + 1, high);
      //开辟一个长度为high-low+1的临时数组
      int[] temp = new int[high - low + 1];
      int L = low, R = mid + 1, tIndex = 0;
      //将[low,mid]有序区间与[mid+1,high]有序区间进行归并存放在临时数组中
      while (L <= mid && R <= high) {
          if (arr[L] < arr[R]) {
              temp[tIndex] = arr[L];
              L++;
          } else {
              temp[tIndex] = arr[R];
              R++;
          }
          tIndex++;
      }
      //System.arraycopy的函数原型是：
      //public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
      //其中：src表示源数组，srcPos表示源数组要复制的起始位置，desc表示目标数组，length表示要复制的长度。
      if (L <= mid) {
          System.arraycopy(arr, L, temp, tIndex, mid - L + 1);
      }
      if (R <= high) {
          System.arraycopy(arr, R, temp, tIndex, high - R + 1);
      }
      //将有序临时数组temp的值赋值到[low,high]区间中
      System.arraycopy(temp, 0, arr, low, temp.length);
  }
  

• 堆排序（Heap Sort）：通过将待排序元素构建成一个最大堆（或最小堆），然后将堆顶元素与末尾元素交*换，再重新调整堆，重复该过程直到排序完成。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)。空间复杂度：O(1)

  //堆排序
  public static void heapSort(int[] arr) {
      //构建大顶堆
      for (int i = arr.length / 2 - 1; i >= 0; i--) {
          //从第一个非叶子结点从下至上，从右至左调整结构
          shifDow(arr, i, arr.length);
      }
      //调整堆结构+交换堆顶元素与末尾元素
      for (int i = arr.length - 1; i > 0; i--) {
          //交换堆顶元素与末尾元素
          int temp = arr[i];
          arr[i] = arr[0];
          arr[0] = temp;
          //调整堆结构
          shifDow(arr, 0, i);
      }
  
  }
  
  //向下调整位置，构建大顶堆
  public static void shifDow(int[] arr, int parent, int len) {
      // 有边界，因为是向下构建，只用到倒数第一个非叶子节点就可以了
      int half = len / 2;
      while (parent < half) {
          //因为parent < half, child的值不可能越界
          int child = parent * 2 + 1;
          int right = child + 1;
          if (right < len && arr[child] < arr[right]) {
              //右节点的值大于左节点的值，将right赋值给child
              child = right;
          }
          //满足小顶堆的性质，break
          if (arr[parent] >= arr[child]) {
              break;
          }
          //交换，较大的值充当父亲
          int temp = arr[parent];
          arr[parent] = arr[child];
          arr[child] = temp;
          // 因为出现了交换，为了保证交换下去的节点也能满足小顶堆，需要继续调整堆
          // 指定parent为child，进入下一次循环
          parent = child;
      }
  }
  

  可以把堆排序的过程大致分为两大步骤，分别是建堆和排序。

  • 建堆：建堆操作就是将一个无序的数组转化为最大堆的操作，首先将数组原地建一个堆。“原地”的含义就是不借助另一个数组，就在原数组上操作。我们的实现思路是从后往前处理数据，并且每个数据都是从上向下调整。
  • 排序：建堆结束后，数组中的数据已经按照大顶堆的特性进行组织了，数组中的第一个元素就是堆顶，也就是最大的元素。我们把它和最后一个元素交换，那最大的元素就放到了下标为n的位置，时末尾元素就是最大值，将剩余元素重新堆化成一个大顶堆。继续重复这些步骤，直至数组有序排列

排序算法相关知识

• 排序稳定性

  • 指在排序过程中，当有多个具有相同关键字的元素时，这些元素在排序后的序列中保持它们原有的相对顺序 具体来说，对于一个序列中的两个元素A和B，如果A和B的键值相同，且在排序前A在B之前，那么在排序后A仍然应该在B之前，算法才能被称为是稳定的
  • 稳定排序算法的特点：
    • 相同元素的相对位置不会改变，排序后仍然保持原始顺序
    • 适用于需要保持元素间相对顺序关系的场景，如按照年龄排序后按姓名排序
  • 不稳定排序算法的特点：
    • 相同元素的相对位置可能会改变，排序后不保证原始顺序
    • 可能会更快，但不适用于需要保持元素间相对顺序关系的场景

• 快排这么强，冒泡排序还有必要吗？

  • 对小规模数据或基本有序的数据，冒泡排序可能比快速排序更简单、更直观。
  • 冒泡排序是稳定排序算法，相对于快速排序的不稳定性，在某些情况下可能更适合要求稳定性的场景。
  • 冒泡排序是原地排序算法，不需要额外的空间，适合空间复杂度要求严格的场景

• 要对一个很大的数据集，进行排序，而没办法一次性在内存排序，怎么办？

  • 将存储着 100 亿数据的文本文件一条一条导入到数据库中，然后根据某个字段建立索引，数据库进行索引排序操作后我们就可以依次提取出数据追加到结果集中
  • 拆分成一个一个的小文件来处理呗，最终再合并成一个排好序的大文件