数据结构与算法概要

说明

假设算法要解决问题的输入规模是 n

概念

• 程序设计 我们的追求是：选择更加合适的 数据结构，使用花费时间更少、占用空间更小的 算法。
• 数据结构的操作一般涉及到 增、删、改、查 共4种情况。
• 算法的时间复杂度衡量一个算法的 执行效率，空间复杂度衡量一个算法的 内存消耗。
• 算法的时间复杂度跟算法中 基本操作 (算法执行中的每一条语句)次数的数量正相关。
• 算法的空间复杂度跟算法内定义的 变量 所占空间和系统为实现 递归 所占的堆栈空间两部分有关。
• 时空复杂度 用 $BigO$ 表示。例如：$O(1)$，$O(n^2)$，$O(logn)$ 。它们都是估计值，仅保留最高阶增长项。例如：$O(n^2+n+1)$ ≈ $O(n^2)$，$O(2n+1)$ ≈ $O(n)$。
• 算法时空复杂度通常指 最坏情况下 的复杂度。
• 常见的时间复杂度有：$O(1)$ < $O(logn)$ < $O(n)$ < $O(nlogn)$ < $O(n^2)$ < $O(n^3)$ < $O(2^n)$ < $O(n!)$ < $O(n^n)$。当$(n>10)$时。
• 常见的空间复杂度有：$O(1)$ < $O(logn)$ < $O(n)$ < $O(n^2)$。

常见的数据结构和算法

基础的 数据结构 和 算法 包括：

• 数据结构：数组、字符串、链表、树 等。
• 算法：分治算法、贪心算法、穷举算法、回溯算法、动态规划 等。

数组

• 数组：是最基础、最简单的数据结构。
• 数组：是一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据，是实现线性表顺序结构存储的基础。
• 数组的最大特点的支持 随机访问。
• 数组的寻址公式：下标 i 对应的数据元素地址 = 数据首地址 + i × 单个数据元素所占内存大小。

冒泡排序算法

• 基本思想：经过多次迭代，通过相邻元素之间的比较与交换，使值较小的元素逐渐移动到前面，值较大的元素移动到后面。
• 步骤：
  • 第 1 趟 冒泡 ：对前 n 个元素执行 冒泡，从而使第 1 个值最大的元素放置在正确位置上。
  • 第 2 趟 冒泡 ：对前 n-1 个元素执行 冒泡，从而使第 2 个值最大的元素放置在正确位置上。
  • 依次类推，重复上述 冒泡 过程，直到某一趟排序过程中不出现元素交换位置的动作，则排序结束。
• 算法分析：
  • 最佳时间复杂度：初始时序列已经是升序排列，只需经过 1 趟排序，总共经过 n 次元素之间的比较，并且不移动元素，算法就可以结束排序，时间复杂度为$O(n)$。
  • 最坏时间复杂度：初始时序列已经是降序排列，或者最小值元素处在序列的最后，则需要进行 n 趟排序，时间复杂度为$O(n^2)$。
  • 空间复杂度：冒泡排序为原地排序算法，只用到指针变量 i、j 以及标志位 flag 等常数项的变量，时间复杂度为$O(1)$。
• 冒泡排序适用情况：冒泡排序法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，冒泡排序方法比较适合于 序列数据量较小 的情况，尤其是当序列的初始状态为 基本有序 的情况。
• 排序稳定性：由于元素交换是在相邻元素之间进行的，不会改变相等元素的相对顺序，因此，冒泡排序法是一种稳定排序算法

选择排序算法

• 基本思想：将数组分为两个区间，左侧有序，右侧无序。每趟从无序区间中选择一个值最小的元素，放到有序区间的末尾，从而将该元素划分到有序区间。
• 步骤:
  • 第 1 趟遍历整个初始数组，标记最小值对应的下标值 i，将 i 处对应的元素和位置 0 处的元素交换位置。
  • 第 2 趟遍历剩余无序区间，任然标记最小值对应的下标值 i,将 i 处对应的元素和无序区间位置 0 处的元素交换位置。
  • 依此类推，重复上述从无序区间中选择最小值元素的操作，直到数组的最后一个元素，则排序结束。
• 算法分析：
  • 时间复杂度：每趟找出最小值元素需要$O(n)$，总共需要走的趟数需要$O(n)$，时间复杂度为$O(n^2)$。
  • 空间复杂度：为原地排序算法，只用到指针变量以及最小值下标变量等常数项变量，空间复杂度$O(1)$。
• 选择排序适用情况：选择排序需要移动较多次数元素，并且排序时间效率比较低，因此适合数组数量规模较小的情况。优点是原地排序无需占用额外空间。
• 排序稳定性：交换过程中有可能改变原本相等元素的相对位置，为不稳定排序算法。

插入排序算法

• 基本思想：将数组分为两个区间，左侧有序，右侧无序。每趟从无序区间中找出一个元素，插入到有序区间的适当位置。
• 步骤:
  • 初始状态，有序区间[0，0]，无序区间[1，n-1]。
  • 第 1 趟插入：取出无序区间第一个元素 arr[1] 当前需要插入的元素。从右到左与有序区间的元素比较，比 arr[1] 大的向后移。第 1 趟结束后数组状态：有序区间[0，1]，无序区间[2，n-1]。
  • 第 2 趟插入：取出无序区间第一个元素 arr[2] 当前需要插入的元素。从右到左与有序区间的元素比较，比 arr[2] 大的向后移。第 2 趟结束后数组状态：有序区间[0，2]，无序区间[3，n-1]。
  • 依此类推，重复上述右侧取数据并与左侧元素对比后的插入操作，直到排序结束。
• 算法分析：
  • 最佳时间复杂度：最好的情况数组是升序排列的，每个元素只进行一次比较，且无需挪到元素的位置。时间复杂度$O(n)$。
  • 最差时间复杂度：最坏的情况数组是降序排列的，每个元素都要进行n-1次比较，时间复杂度是$O(n^2)$。
  • 平均时间复杂度：数组随机排列，取最好和最坏的平均值，时间复杂度是$O(n^2)$。
  • 空间复杂度：为原地排序算法，只用到指针变量以及每次取出的常量值变量，空间复杂度$O(1)$。
  • 排序稳定性：在插入过程中，每次都将元素插入到相等元素的右侧，并不会改变元素的相对位置，为稳定排序算法。

希尔排序算法

• 基本思想：将整个数组按照一定的间隔划分成若干子数组，每个子数组分别进行插入排序。然后缩小间隔进行下一轮划分子数组和对子数组进行插入排序，直到最后一轮排序间隔为1，对整个数组进行插入排序。
• 步骤：
  • 确定元素间隔数 gap。
  • 将数组按照间隔数从第 1 个元素开始一次性分成若干个子数组，即将所有位置间隔为 gap 的元素视为一个子数组。
  • 将子数组按照插入排序进行排序。
  • 减少间隔数再将整个数组按照新的间隔分成若干子数组，再分别对各个子数组进行排序。
  • 依此类推，直到间隔 gap 值为1，进行最后一次排序，结束排序。
• 算法分析:
  • 时间复杂度：介于$O(nlogn)$ < $O(n^2)$之间。
  • 空间复杂度：排序中用到的插入排序是原地排序，变量都为常数级别，空间复杂度为$O(1)$。
  • 排序稳定性：在一次插入排序中是稳定的，但在不同的插入排序中，相等元素可能在各自的插入排序中移动位置。总体为不稳定排序。

归并排序算法

• 基本思想：采用经典的分治策略，先递归地将当前数组平均分成两半，然后将有序数组两两合并，最终合并成一个有序数组。
• 步骤：
  • 分解过程：先递归地将数组平均分成两半，直到子数组长度为1。
    • 找到数组中心位置 mid，从中心位置将数组分成左右两个子数组 left_arrs，right_arrs。
    • 对左右两个子数组 left_arrs，right_arrs 分别进行递归分解。
    • 最终将数组分解成 n 个长度为 1的子数组。
  • 归并过程：从长度为 1 的有序子数组开始，依次将有序子数组两两合并，直到合并成一个长度为 n 的有序数组。
    • 使用数组变量存放合并后的有序数组。
    • 使用两个指针 left_i，right_i 分别指向两个数组 left_arrs 、right_arrs 的起始位置。比较两数组的首元素，将较小的元素存放到结果数组中。
    • 移动指针到下一位置，重复上述两数组首元素的大小比较操作，直到数组末尾。
• 算法分析：
  • 最佳\最坏\平均时间复杂度：$O(nlogn)$。
  • 空间复杂度：需要额外的空间存储临时数组，空间复杂度为$O(n)$。
• 算法适用场景：大规模数据集排序和需要稳定排序的场合。
• 排序稳定性：归并排序是稳定的排序算法，不会改变相同元素的相对顺序。