以下是计算机专业中被普遍认为是“默认大家都会”的底层基础算法与数据结构知识点，这些是构建更高级知识的基石。

一、基础排序算法这些是理解算法思想的起点，必须掌握其原理、代码和时间/空间复杂度。

// 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[j+1]
                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; // 插入到正确位置 }
}

二、基础查找算法

在有序和无序数据中查找元素的基本方法。

// 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; // 未找到
}

三、基础数据结构操作

对数组、链表、栈、队列等基本结构的增删改查是必须掌握的基本功。

1. 数组

   • 随机访问：通过索引 arr[i] 在 O(1) 时间内访问。
   • 插入/删除：在非末尾位置操作需要移动后续元素，平均 O(n)。

2. 链表 (单向)

   • 节点结构：包含数据域和指向下一个节点的指针。
   • 插入/删除：在已知节点位置时，通过修改指针可在 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;       // 新节点成为新的头节点
}

1. 栈

   • 后进先出：只允许在栈顶进行插入（入栈，push）和删除（出栈，pop）操作。
   • 应用：函数调用栈、括号匹配、表达式求值。

2. 队列

   • 先进先出：在队尾插入（入队，enqueue），在队头删除（出队，dequeue）。
   • 应用：广度优先搜索、任务调度、消息队列。

四、基础算法思想

这是解决问题的通用范式。

1. 枚举/暴力

   • 思想：列举所有可能的情况，并检查每种情况是否满足条件。
   • 要点：通常需要多层循环，时间复杂度高，但易于理解和实现。

2. 递归

   • 思想：函数直接或间接调用自身，将大问题分解为相似的小问题。
   • 三要素：基线条件（递归终止条件）、递归调用、向基线条件推进。
   • 经典问题：阶乘、斐波那契数列、汉诺塔、二叉树遍历。

// 递归计算阶乘 n!
int factorial(int n) {
    if (n == 0 || n == 1) { // 基线条件
        return 1;
    }
    return n * factorial(n - 1); // 递归调用，问题规模减小
}

1. 分治
   • 思想：将原问题分解成若干个规模较小的子问题，递归解决子问题，然后合并子问题的解得到原问题的解。
   • 经典算法：归并排序、快速排序、二分查找。

五、复杂度分析基础

这是评价算法优劣的标尺，必须会算、会说。

• 时间复杂度：表示算法执行时间随数据规模增长的变化趋势。常用大O表示法。
  • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• 空间复杂度：表示算法在执行过程中临时占用存储空间的大小随数据规模增长的变化趋势。
• 分析方法：关注循环嵌套层数、递归深度、辅助数据结构的大小。

总结：以上算法与数据结构是计算机科学的“普通话”，是阅读更复杂代码、学习高级课程（如操作系统、数据库、编译原理）和通过技术面试的必备前提。掌握它们的关键在于理解思想、亲手实现、分析复杂度，而不仅仅是背诵。

参考来源

• 算法与数据结构学习笔记——常见简单排序算法详解
• 3.（下）冒泡排序法（循环嵌套）
• 数据结构八大排序详解（一）：四大简单排序-CSDN博客
• c语言中交换排序 - 腾讯云开发者社区 - 腾讯云
• 新版数据结构与算法零基础到精通156集（全）