下面为每类算法赋予贴合原理的趣味名称同时从核心思想、执行步骤、复杂度、C 实现代码、算法特点五个维度做详细讲解全部代码可直接编译运行。一、四大经典排序算法1. 快速排序 →标杆劈叉法核心思想选一个元素作为「标杆」遍历数组后把比标杆小的元素全放左边比标杆大的全放右边标杆直接落到自己的最终正确位置像 “劈叉” 一样把数组切成两半再对左右两个子数组重复这个操作直到所有元素都归位。是分治思想的典型代表。执行步骤选标杆通常选数组首元素、尾元素或中间元素作为基准值分区操作用双指针从两端向中间遍历把小于标杆的元素换到左侧大于标杆的换到右侧最后把标杆放到分界点递归分治对标杆左侧、右侧的子数组分别重复前两步直到子数组长度为 1复杂度平均时间O(nlogn)最坏时间O(n²)数组已有序且选端点当标杆时可通过随机选标杆优化空间复杂度O(logn)递归调用栈稳定性不稳定C 实现cpp运行#include vector using namespace std; // 分区函数返回标杆最终位置 int partition(vectorint nums, int left, int right) { int pivot nums[left]; // 选左端点当标杆 while (left right) { // 从右往左找第一个小于标杆的数 while (left right nums[right] pivot) right--; nums[left] nums[right]; // 从左往右找第一个大于标杆的数 while (left right nums[left] pivot) left; nums[right] nums[left]; } nums[left] pivot; // 标杆归位 return left; } void quickSort(vectorint nums, int left, int right) { if (left right) return; int pivotPos partition(nums, left, right); quickSort(nums, left, pivotPos - 1); // 递归左半区 quickSort(nums, pivotPos 1, right); // 递归右半区 }2. 堆排序 →金字塔淘汰赛核心思想把数组构造成「大顶堆」金字塔结构塔顶永远是最大元素每次把塔顶的 “冠军” 元素和堆尾元素交换相当于冠军晋级最终排名再把剩下的元素重新调整成堆选出下一个冠军重复这个过程直到所有元素都排好序。执行步骤建堆从最后一个非叶子节点开始从下往上把数组调整为大顶堆交换堆顶将堆顶最大元素与堆尾元素交换堆的有效长度减 1下沉调整对新的堆顶元素做下沉操作维持大顶堆性质重复步骤 2、3直到堆的有效长度为 1复杂度时间复杂度O(nlogn)建堆 O (n) n 次调整 O (logn)时间稳定空间复杂度O(1)原地排序无额外空间稳定性不稳定C 实现cpp运行#include vector using namespace std; // 下沉调整维持大顶堆性质 void heapify(vectorint nums, int n, int i) { int largest i; // 父节点 int left 2 * i 1; // 左孩子 int right 2 * i 2; // 右孩子 if (left n nums[left] nums[largest]) largest left; if (right n nums[right] nums[largest]) largest right; if (largest ! i) { swap(nums[i], nums[largest]); heapify(nums, n, largest); // 递归调整被交换的子节点 } } void heapSort(vectorint nums) { int n nums.size(); // 1. 构建大顶堆 for (int i n / 2 - 1; i 0; i--) { heapify(nums, n, i); } // 2. 逐个取出堆顶元素 for (int i n - 1; i 0; i--) { swap(nums[0], nums[i]); // 堆顶与堆尾交换 heapify(nums, i, 0); // 调整剩余堆 } }3. 归并排序 →百川归海法核心思想典型的「先分后合」思路先把数组层层拆分直到拆成一个个单独的元素像无数条小溪单个元素天然有序再把有序的小数组两两合并逐步汇成更大的有序数组最终合并成完整的有序数组如同百川汇入大海。执行步骤拆分把数组从中间切成左右两部分递归拆分直到每个子数组只有 1 个元素合并创建临时数组把两个有序子数组按大小顺序合并成一个有序数组逐层向上合并直到得到完整有序数组复杂度时间复杂度O(nlogn)拆分 logn 层每层合并 O (n)时间稳定空间复杂度O(n)需要临时数组存合并结果稳定性稳定排序C 实现cpp运行#include vector using namespace std; // 合并两个有序区间 [left,mid] 和 [mid1,right] void merge(vectorint nums, int left, int mid, int right, vectorint temp) { int i left, j mid 1, k 0; // 按大小顺序合并到临时数组 while (i mid j right) { if (nums[i] nums[j]) temp[k] nums[i]; else temp[k] nums[j]; } // 处理剩余元素 while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; // 拷贝回原数组 for (i 0; i k; i) nums[left i] temp[i]; } void mergeSort(vectorint nums, int left, int right, vectorint temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid, temp); // 递归拆分左半 mergeSort(nums, mid 1, right, temp); // 递归拆分右半 merge(nums, left, mid, right, temp); // 合并两个有序区间 } // 对外调用接口 void mergeSort(vectorint nums) { vectorint temp(nums.size()); mergeSort(nums, 0, nums.size() - 1, temp); }4. 希尔排序 →缩步插缝法核心思想插入排序的优化版。插入排序在数组基本有序时效率极高希尔排序就利用这一点先按大步长把数组分成多组每组内做插入排序让数组先 “大概有序”再逐步缩小步长精细调整直到步长缩为 1此时数组已经接近有序最后做一遍普通插入排序即可完成。执行步骤设定初始步长gap通常取数组长度的 1/2按 gap 分组所有下标相差 gap 的元素为一组每组内执行插入排序缩小 gap通常减半重复分组排序直到 gap 1完成最后一次插入排序数组有序复杂度平均时间O(n^1.3)步长选择不同复杂度有差异最坏时间O(n²)空间复杂度O(1)原地排序稳定性不稳定C 实现cpp运行#include vector using namespace std; void shellSort(vectorint nums) { int n nums.size(); // 逐步缩小步长 gap for (int gap n / 2; gap 0; gap / 2) { // 对每组进行插入排序 for (int i gap; i n; i) { int temp nums[i]; int j; // 组内向前找插入位置 for (j i; j gap nums[j - gap] temp; j - gap) { nums[j] nums[j - gap]; } nums[j] temp; } } }二、基础查找算法二分查找 →折半寻宝术核心思想在有序数组中查找目标值每次都取区间中间的元素和目标对比相等 → 直接找到目标更小 → 目标只可能在左半区直接砍掉右半区目标更大 → 目标只可能在右半区直接砍掉左半区像折木棍一样每次砍掉一半范围效率极高。前提条件数组必须是有序的升序 / 降序均可这里以升序为例。复杂度时间复杂度O(logn)n 个元素最多折 log₂n 次空间复杂度O(1)迭代版C 实现迭代版 递归版cpp运行#include vector using namespace std; // 迭代版推荐无递归栈开销 int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (nums[mid] target) return mid; // 找到目标 else if (nums[mid] target) left mid 1; // 去右半区找 else right mid - 1; // 去左半区找 } return -1; // 未找到 } // 递归版 int binarySearchRecur(vectorint nums, int left, int right, int target) { if (left right) return -1; int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) return binarySearchRecur(nums, mid 1, right, target); else return binarySearchRecur(nums, left, mid - 1, target); }特点查找效率极高适合海量静态有序数据缺点依赖有序数组不适合频繁插入、删除的动态数据谢谢