C语言：笔试高频算法精解

前言本篇承接 C 语言基础语法与工程化能力模块聚焦笔试手撕代码核心高频考点系统覆盖排序、查找、字符串三大必考模块从基础算法原理、标准手撕实现到笔试真题变种全覆盖所有代码贴合笔试答题规范兼顾边界条件与代码鲁棒性是 C 语言岗位求职笔试冲刺的核心必备内容适合零基础入门算法、校招社招笔试复盘与面试突击复习。一、排序算法全解排序是算法与数据结构的基础也是笔试手撕代码的第一大高频题型考察重点不仅是能写出来更要掌握时间 / 空间复杂度、稳定性、适用场景与边界处理。算法核心指标对比表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学演示、小规模近乎有序数据选择排序O(n²)O(n²)O(1)不稳定小规模数据、交换次数少的场景插入排序O(n²)O(n²)O(1)稳定小规模、近乎有序数据性能优于冒泡快速排序O(nlogn)O(n²)O(logn)不稳定通用场景绝大多数情况性能最优归并排序O(nlogn)O(nlogn)O(n)稳定海量数据、外部排序、要求稳定的场景稳定性定义两个相等的元素排序后相对位置保持不变则为稳定排序。1. 冒泡排序核心思想相邻元素两两比较大的往后交换每一轮将当前最大的元素 “冒泡” 到末尾。手撕实现void bubbleSort(int* arr, int len) { if (arr NULL || len 1) return; for (int i 0; i len - 1; i) { int flag 0; // 优化标记本轮是否发生交换 for (int j 0; j len - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换 int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; flag 1; } } if (flag 0) break; // 本轮无交换已有序提前退出 } }考点优化版 flag 的作用当某一轮遍历没有发生任何交换说明数组已经完全有序直接提前终止最好时间复杂度可优化到 O (n)。2. 快速排序笔试最高频核心思想分治思想选一个基准值将数组分为小于基准和大于基准两部分再递归排序左右两个子区间。霍尔分区法左右指针法// 分区函数返回基准值最终位置 int partition(int* arr, int left, int right) { int key arr[left]; // 选最左为基准 while (left right) { // 右指针往左找小于基准的值 while (left right arr[right] key) { right--; } arr[left] arr[right]; // 左指针往右找大于基准的值 while (left right arr[left] key) { left; } arr[right] arr[left]; } arr[left] key; // 基准值归位 return left; } // 快排主函数 void quickSort(int* arr, int left, int right) { if (left right) return; int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); // 递归排左区间 quickSort(arr, pivot 1, right); // 递归排右区间 }高频考点最坏情况数组已有序时每次分区都极不均匀时间复杂度退化为 O (n²)优化方法随机选基准、三数取中法选基准空间复杂度递归调用栈的开销平均 O (logn)最坏 O (n)不稳定交换过程会打乱相等元素的相对顺序适用场景通用排序首选绝大多数场景性能最优是面试必背代码3. 归并排序核心思想分治思想将数组不断二分拆分为子序列再将有序子序列合并为完整有序数组。手撕实现// 合并两个有序区间 [left, mid] 和 [mid1, right] void merge(int* arr, int left, int mid, int right, int* tmp) { int i left; // 左区间起点 int j mid 1; // 右区间起点 int k left; // 临时数组下标 // 按序合并 while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } // 拷贝剩余元素 while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; // 拷回原数组 for (i left; i right; i) { arr[i] tmp[i]; } } // 归并排序主函数 void mergeSort(int* arr, int left, int right, int* tmp) { if (left right) return; int mid left (right - left) / 2; // 避免溢出 mergeSort(arr, left, mid, tmp); mergeSort(arr, mid 1, right, tmp); merge(arr, left, mid, right, tmp); }高频考点优势最坏时间复杂度依然是 O (nlogn)性能稳定且是稳定排序缺点需要 O (n) 额外空间空间复杂度高适用场景海量数据排序、外部排序、要求排序稳定的场景二、查找算法核心查找是笔试第二大基础题型其中二分查找是最高频考点核心考察边界条件处理与变种问题。1. 基础二分查找适用场景有序数组的目标值查找时间复杂度 O (logn)远快于遍历查找 O (n)。标准循环实现闭区间写法// 找到返回下标找不到返回-1 int binarySearch(int* arr, int len, int target) { if (arr NULL || len 0) return -1; int left 0; int right len - 1; // 闭区间 [left, right] while (left right) { int mid left (right - left) / 2; // 防止溢出 if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; // 目标在右半区 } else { right mid - 1; // 目标在左半区 } } return -1; }核心细节mid left (right - left) / 2替代(leftright)/2避免两数相加溢出闭区间对应循环条件left right边界更新为mid±1是最不易出错的标准写法2. 二分查找高频变种变种 1查找第一个等于目标值的位置int findFirst(int* arr, int len, int target) { int left 0; int right len - 1; int res -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { res mid; // 记录位置 right mid - 1; // 继续往左找更早的 } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return res; }变种 2查找最后一个等于目标值的位置int findLast(int* arr, int len, int target) { int left 0; int right len - 1; int res -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { res mid; left mid 1; // 继续往右找更晚的 } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return res; }二分变种核心思路找到目标时不立刻返回继续向目标方向收缩区间直到锁定边界。三、字符串高频手撕题字符串操作是 C 语言笔试的常驻题型本质考察指针操作与内存边界意识常考标准库函数的手动实现。1. 手写 strlen求字符串长度size_t myStrlen(const char* str) { assert(str ! NULL); size_t len 0; while (*str ! \0) { len; str; } return len; }考点必须校验空指针以\0为结束标志2. 手写 strcpy字符串拷贝char* myStrcpy(char* dest, const char* src) { assert(dest ! NULL src ! NULL); char* ret dest; // 保存目标起始地址 while ((*dest *src) ! \0) { ; } return ret; }考点源字符串加 const 保护返回目标地址支持链式调用会拷贝结束符3. 手写 strcmp字符串比较int myStrcmp(const char* s1, const char* s2) { assert(s1 ! NULL s2 ! NULL); while (*s1 *s2 *s1 ! \0) { s1; s2; } return *s1 - *s2; // 大于返回正数等于返回0小于返回负数 }4. 字符串反转void reverseString(char* str) { assert(str ! NULL); int left 0; int right myStrlen(str) - 1; while (left right) { char tmp str[left]; str[left] str[right]; str[right] tmp; left; right--; } }四、笔试高频真题精选真题 1数组原地去重有序数组题目给你一个有序数组原地删除重复出现的元素返回去重后的新长度。思路快慢指针慢指针指向最后一个不重复元素快指针遍历遇到不同元素就更新慢指针。int removeDuplicates(int* nums, int numsSize) { if (numsSize 1) return numsSize; int slow 0; for (int fast 1; fast numsSize; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }真题 2两数之和题目给定一个整数数组和一个目标值找出数组中和为目标值的两个数的下标。思路暴力解法双层循环 O (n²)笔试基础写法进阶可用哈希表 O (n)。// 暴力解法笔试基础版 int* twoSum(int* nums, int numsSize, int target, int* returnSize) { *returnSize 2; int* res (int*)malloc(sizeof(int) * 2); for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { res[0] i; res[1] j; return res; } } } free(res); *returnSize 0; return NULL; }真题 3最长公共前缀题目编写一个函数查找字符串数组中的最长公共前缀。char* longestCommonPrefix(char** strs, int strsSize) { if (strsSize 0) return ; // 以第一个字符串为基准 for (int i 0; strs[0][i] ! \0; i) { char c strs[0][i]; // 逐个对比其他字符串的对应位置 for (int j 1; j strsSize; j) { if (strs[j][i] ! c || strs[j][i] \0) { // 出现不同或字符串结束截断返回 strs[0][i] \0; return strs[0]; } } } return strs[0]; }五、面试高频考点与易错坑点1. 经典面试问答Q1快速排序的时间复杂度是多少最坏情况是什么怎么优化答 平均时间复杂度 O (nlogn)最坏 O (n²)。 最坏情况出现在数组完全有序或完全逆序时每次分区极不均匀退化为冒泡排序。 优化方法随机选择基准值避免有序数组最坏情况三数取中法选基准降低极端情况概率数据量较小时切换为插入排序减少递归开销Q2哪些排序是稳定的哪些不稳定答 稳定排序冒泡排序、插入排序、归并排序、基数排序 不稳定排序选择排序、快速排序、堆排序、希尔排序 判断核心排序过程中相等元素的相对顺序是否会被交换打乱。Q3二分查找的前提条件是什么有哪些常见变种答 前提数组必须有序且支持随机访问数组适用链表不适用。 常见变种查找第一个等于目标值的位置、查找最后一个等于目标值的位置、查找第一个大于等于目标值的位置、查找最后一个小于等于目标值的位置。Q4手写字符串函数为什么要校验空指针为什么源指针要加 const答 校验空指针是为了避免解引用空指针导致段错误提升代码鲁棒性是工程代码的基本规范。 源指针加 const 是为了保护源字符串不被意外修改同时可以接收 const 字符串参数提升函数通用性符合 const 正确性原则。Q5归并排序和快速排序各有什么优缺点分别适用什么场景答 快排优点平均性能好、原地排序空间开销小缺点不稳定、最坏时间复杂度差。 归并优点性能稳定、最坏依然 O (nlogn)、稳定排序缺点需要额外 O (n) 空间。 适用场景通用排序优先快排要求排序稳定、数据量大、外部排序场景用归并。2. 常见易错坑点快排分区边界处理错误导致死循环或数组越界二分查找 mid 计算用(leftright)/2大数场景下溢出字符串操作忘记\0结束符拷贝、比较时出现越界排序算法忘记做空数组、单元素的边界校验二分变种找到目标直接返回不会收缩区间查找边界字符串函数不校验空指针传入 NULL 直接崩溃归并排序忘记申请临时数组或临时数组重复申请释放导致性能低下以上就是 C 语言笔试最核心的经典算法手撕内容覆盖排序、查找、字符串三大必考模块建议重点掌握快排、归并、二分查找与字符串函数实现是绝大多数公司笔试的常驻题型。制作不易如果对你有用希望能点赞收藏支持一下。