《算法武林谱：四大排序神功与二分寻宝术全解》-北京尧图网络

下面为每类算法赋予贴合原理的趣味名称同时从核心思想、执行步骤、复杂度、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); }特点查找效率极高适合海量静态有序数据缺点依赖有序数组不适合频繁插入、删除的动态数据谢谢

《算法武林谱：四大排序神功与二分寻宝术全解》

相关推荐

web-serial-monitor —— 免安装的浏览器端串口 / 蓝牙 / WebSocket 调试平台

现代化BI的选型清单：CEO视角下的五个关键决策点

Recoll离线版文本搜索工具：专为银河麒麟系统优化，支持龙芯3A6000国产平台免联网安装

更多资讯

qgeval：轻量级文本生成评估工具包，支持BLEU/METEOR/ROUGE三指标统一计算

自动控制原理实验全攻略：从传递函数到Simulink仿真与稳定性分析

基于理查逊直线法的金属逸出功测量实验：原理、实现与误差分析

Java课程设计实战：基于Swing+MyBatis+MySQL的ATM柜员机模拟系统

舒尔特表格：科学提升注意力的视觉训练工具

UrsAI2Paho+AI2：MQTT扩展包配置与避坑全攻略

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？