以下是计算机专业中被普遍认为是“默认大家都会”的底层基础算法与数据结构知识点这些是构建更高级知识的基石。一、基础排序算法这些是理解算法思想的起点必须掌握其原理、代码和时间/空间复杂度。算法名称核心思想时间复杂度 (平均/最坏)空间复杂度稳定性代码实现要点冒泡排序重复遍历相邻元素两两比较并交换将最大/小元素“冒泡”到一端。O(n²) / O(n²)O(1)稳定双层循环内层循环边界随外层递增而缩小。选择排序每轮在未排序序列中找到最小或最大元素存放到已排序序列的末尾。O(n²) / O(n²)O(1)不稳定双层循环外层标记当前位置内层寻找最小元素索引后进行交换。插入排序将待排序元素插入到前面已经排好序的序列中的适当位置如同整理扑克牌。O(n²) / O(n²)O(1)稳定从第二个元素开始向前比较并移动元素找到插入位置。// 1. 冒泡排序 (基础版) void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { // 遍历轮数 for (int j 0; j n - i1; j) { // 每轮比较范围递减 if (arr[j] arr[j 1]) { // 相邻元素比较 // 交换 arr[j] 和 arr[j1] int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } } // 优化可设置标志位若某轮无交换则提前终止。 // 2. 选择排序 void selectionSort(int arr[], int n) { for (int i 0; i n1; i) { int minIndex i; // 假设当前位置是最小值 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; // 更新最小元素索引 } } // 将找到的最小元素与第i个位置交换 int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } } // 3. 插入排序 void insertionSort(int arr[], int n) { for (int i 1; i n; i) { // 从第二个元素开始 int key arr[i]; // 待插入的元素 int j i1; // 将大于key的元素向后移动 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; // 插入到正确位置 } }二、基础查找算法在有序和无序数据中查找元素的基本方法。算法名称适用条件核心思想时间复杂度代码实现要点顺序查找无序或有序序列从头到尾逐个比较直到找到目标或遍历完。O(n)单层循环简单直接。二分查找有序序列每次与中间元素比较将搜索范围缩小一半。O(log n)循环或递归维护low、high、mid三个指针。// 1. 顺序查找 int sequentialSearch(int arr[], int n, int target) { for (int i 0; i n; i) { if (arr[i] target) { return i; // 找到返回索引 } } return -1; // 未找到 } // 2. 二分查找 (迭代版) int binarySearch(int arr[], int n, int target) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; // 防止溢出 if (arr[mid] target) { return mid; } else if (arr[mid] target) { low mid 1; // 目标在右半部分 } else { high mid - 1; // 目标在左半部分 } } return -1; // 未找到 }三、基础数据结构操作对数组、链表、栈、队列等基本结构的增删改查是必须掌握的基本功。数组随机访问通过索引arr[i]在 O(1) 时间内访问。插入/删除在非末尾位置操作需要移动后续元素平均 O(n)。链表 (单向)节点结构包含数据域和指向下一个节点的指针。插入/删除在已知节点位置时通过修改指针可在 O(1) 时间内完成。遍历查找需要从头节点开始时间复杂度 O(n)。// 单向链表节点定义与头插法示例 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 在链表头部插入新节点 ListNode* insertAtHead(ListNode* head, int val) { ListNode* newNode new ListNode(val); newNode-next head; // 新节点指向原头节点 return newNode; // 新节点成为新的头节点 }栈后进先出只允许在栈顶进行插入入栈push和删除出栈pop操作。应用函数调用栈、括号匹配、表达式求值。队列先进先出在队尾插入入队enqueue在队头删除出队dequeue。应用广度优先搜索、任务调度、消息队列。四、基础算法思想这是解决问题的通用范式。枚举/暴力思想列举所有可能的情况并检查每种情况是否满足条件。要点通常需要多层循环时间复杂度高但易于理解和实现。递归思想函数直接或间接调用自身将大问题分解为相似的小问题。三要素基线条件递归终止条件、递归调用、向基线条件推进。经典问题阶乘、斐波那契数列、汉诺塔、二叉树遍历。// 递归计算阶乘 n! int factorial(int n) { if (n 0 || n 1) { // 基线条件 return 1; } return n * factorial(n - 1); // 递归调用问题规模减小 }分治思想将原问题分解成若干个规模较小的子问题递归解决子问题然后合并子问题的解得到原问题的解。经典算法归并排序、快速排序、二分查找。五、复杂度分析基础这是评价算法优劣的标尺必须会算、会说。时间复杂度表示算法执行时间随数据规模增长的变化趋势。常用大O表示法。O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)空间复杂度表示算法在执行过程中临时占用存储空间的大小随数据规模增长的变化趋势。分析方法关注循环嵌套层数、递归深度、辅助数据结构的大小。总结以上算法与数据结构是计算机科学的“普通话”是阅读更复杂代码、学习高级课程如操作系统、数据库、编译原理和通过技术面试的必备前提。掌握它们的关键在于理解思想、亲手实现、分析复杂度而不仅仅是背诵。参考来源算法与数据结构学习笔记——常见简单排序算法详解3.下冒泡排序法循环嵌套数据结构八大排序详解一四大简单排序-CSDN博客c语言中交换排序 - 腾讯云开发者社区 - 腾讯云新版数据结构与算法零基础到精通156集全