排序查找工程化模板：从二分边界到快排稳定性的实践指南

1. 从“每次现场推导”到“闭眼能写”：模板的价值在哪

排序和查找，两个听起来基础到不能再基础的操作，但我在笔试、面试和日常开发里见过太多人在同一类边界问题上反复翻车。快排的 partition 边界到底怎么收？二分查找的 while 里到底写 < 还是 <=？mid 要不要加 1？这些细节如果每次都靠现场推导，不仅慢，而且容易错。更关键的是，排序查找并不是“会写就行”的零散技巧，它是一整套可以沉淀成模板的思维框架。

我最早意识到模板的价值，是带新人写代码的时候。同一个二分查找，三个人写出了三种边界处理方式，逻辑上都能跑，但风格迥异，互相 review 的成本很高。后来我统一了写法，要求全组用同一套“左闭右开”或“左闭右闭”的模板，代码可读性和 bug 率立刻有了明显改善。所以这篇文章不是教科书式地讲算法原理，而是从实际使用角度，分享一套我反复验证过、可以直接抄作业的排序查找模板，以及每个模板背后的取舍逻辑。

如果你是刚学数据结构的初学者，这篇文章可以帮你少走弯路；如果你已经工作几年，但每次遇到手写排序、二分查找还是心里发虚，那这套模板同样适合你。我会尽量把“为什么这样写”讲清楚，而不是只丢给你几段代码。

1.1 为什么排序查找是最适合做成模板的算法

排序和查找和别的算法不一样，它们有两个天然属性：一是使用频率极高，二是边界条件极多。频率高意味着你值得花时间把写法固定下来；边界多意味着如果你不固定写法，每次都会在同样的地方消耗脑力。

比如排序，不管是大顶堆还是小顶堆，不管升序还是降序，底层无非是比较和交换。只要把比较器、交换逻辑和越界判断固化下来，剩下的都是套用。查找也一样，顺序查找、二分查找、边界查找，本质上都在回答同一个问题：“目标元素在数据集合里的什么位置？”

还有一个容易忽略的点：排序和查找经常是组合出现的。先排序再二分、先排序再去重、先排序再合并区间，这些组合场景如果每次都单独重写，很容易在接口上出问题。模板的意义就是把“排序”和“查找”这两块积木打磨好，让它们能稳定地拼接。

1.2 模板不等于死记硬背

有人可能会担心：背模板是不是太机械？我的看法是，模板和死记硬背完全是两回事。死记硬背是不知道原理地背代码，模板则是在理解原理的前提下，把“容易出错的细节”用固定写法锁死。

举个例子，二分查找里 mid = left + Math.floor((right - left) / 2) 这个写法，熟悉的人都知道是为了防止 left + right 在极端情况下溢出。但很多人只是记住了这个公式，没有理解它背后的逻辑。我写模板时，会特意把这一类“有历史教训”的写法标注出来，而不是简单复制。这样模板才能越用越灵活，而不是越来越僵硬。

模板的核心价值是“减少每次决策的认知负担”。当你把边界处理、循环条件、返回值行为都确定下来之后，真正的精力就可以放在更高层的问题上：这个场景适不适合用二分？要不要先排序？空间复杂度能不能接受？

2. 排序模板：手写排序前要清楚的几个固定动作

排序这部分，我想先泼一盆冷水：日常业务开发里，超过九成的场景应该直接用语言内置的排序，不要手写。但笔试、面试、以及某些特殊场景（比如需要稳定排序、需要自定义比较器、需要在大数据量下控制内存）会逼你手写。这时候，一套固定模板就是救命稻草。

我见过的最常见的三个翻车点，几乎每次都一样：交换逻辑写错导致数据丢失、循环边界多算一位或者少算一位、递归排序时没有处理空数组和单元素数组。这三个问题完全可以通过固定模板规避。

2.1 手写排序前的三个固定决策

手写排序前，我会先做三个固定决策：用什么排序算法、升序还是降序、要不要保证稳定。这三个决策定了，模板才能定。

第一个决策：选算法。 如果数据量小（比如几百个），插入排序或者冒泡排序完全够用，代码简单、不容易错。如果数据量大，快排是默认选择，但要注意最坏情况；归并排序适合需要稳定性的场景；堆排序适合需要原地排序且不要求稳定性的场景。

第二个决策：升降序。 我建议在模板里只写升序，降序通过反转比较器实现。这样代码里只有一种逻辑，心智负担最小。

第三个决策：稳定性。 如果需要稳定排序（相同值的元素保持原始相对顺序），别选快排和堆排，直接上归并。

我个人的常用模板组合是：快速排序应付大多数手写场景，归并排序应付稳定排序场景，插入排序应付小数据量场景。这三个模板的代码骨架高度相似，都是“递归分治 + 边界判断”，容易记忆，也容易验证。

2.2 快速排序模板：最坏情况的兜底设计

快速排序是手写排序里出场率最高的，因为它平均性能好、原地排序省内存。但快排有个著名的坑：对已经有序的数组，如果每次都选最左边或最右边的元素作基准，时间复杂度会退化到 O(n²)。我见过很多人手写快排时在这里栽跟头。

我的模板里有一个固定动作：基准元素不选首尾，选中间位置，并且先把基准换到最左边。 这样可以很大程度上避免有序数组的退化问题。当然严格来说，最稳妥的是随机选基准，但取中间值在工程上已经能覆盖绝大多数测试数据，而且代码更稳定、可复现。

javascript复制function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;

    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

function partition(arr, left, right) {
    // 取中间位置作为基准，并交换到最左边，降低有序数组下的退化概率
    const mid = left + Math.floor((right - left) / 2);
    [arr[left], arr[mid]] = [arr[mid], arr[left]];

    const pivot = arr[left];
    let i = left;
    let j = right;

    while (i < j) {
        // 从右向左找第一个小于 pivot 的元素
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];

        // 从左向右找第一个大于 pivot 的元素
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }

    arr[i] = pivot;
    return i;
}

注意这里两个内层 while 的边界条件，i < j 必须写在最前面。如果漏掉，出现 i 超过 j 的情况后，基准归位的位置就会错。这是我见过最频繁的翻车点，没有之一。

另外，快排是不稳定排序。如果业务上有“相同值保持原有顺序”的需求，别用快排硬扛，换归并排序更稳妥。这个选择不是性能问题，是正确性问题。

2.3 归并排序模板：稳定排序的默认答案

归并排序的思路是“先拆后合”，拆到单元素，然后两两合并。它的最大优势是稳定，而且无论数据是否有序，时间复杂度都是稳定的 O(n log n)。代价是需要额外空间，空间复杂度为 O(n)。

我在需要稳定排序的场合，几乎不加思考就套用下面这个模板：

javascript复制function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    // 把剩余元素接上
    while (i < left.length) {
        result.push(left[i]);
        i++;
    }
    while (j < right.length) {
        result.push(right[j]);
        j++;
    }

    return result;
}

归并排序的模板里，我唯一会反复检查的地方就是 merge 函数末尾的两个 while。很多人会写成 if，结果只拼接了一个元素，剩下的全丢了。实际上这两个循环处理的是“两边长度不等”时的收尾，属于必须存在的固定动作。

还有一个小细节：left[i] <= right[j] 里的 <= 决定了合并后的稳定性。如果写成 <，相同元素会优先取右侧的，稳定性就被破坏了。这个符号是稳定排序的关键，值得特意记一下。

2.4 真实场景里我到底会不会手写排序

很多人问我：现在编程语言都自带 sort()，那手动实现排序还有意义吗？我的回答是：意义不在生产环境里复制一遍快排，而在于理解排序行为背后的逻辑。

比如 JavaScript 的 Array.prototype.sort()，不同引擎的底层实现并不一样。V8 对短数组用插入排序，长数组用 TimSort（一种结合归并和插入的混合排序）。如果你不理解这些，你在排序自定义对象时就会疑惑：为什么我的排序结果有时候稳定有时候不稳定？为什么对一个已经排好序的大数组排序反而很慢？

再比如，SQL 里的 ORDER BY、Excel 里的排序、前端表格点击表头排序，底层都是排序算法。理解原理之后，你就能预判性能瓶颈在哪里，遇到“数据大到内存放不下”的场景也知道该往哪个方向去解决。所以手写排序模板更大的价值是“理解”，而不是“替代”。

3. 查找模板：二分边界处理是我见过翻车最多的地方

查找算法里，顺序查找没什么可说的，就是一个循环逐个比对。真正需要小心的是二分查找，因为它依赖于数据有序，而且边界条件极其容易写错。

我刷题和带人的经验是：二分查找的翻车率远高于快排。常见的错误包括：while 循环进不去或死循环、mid 计算溢出、找到目标后返回了错误的位置、没有找到时返回的语义不统一。这些问题都不是“不会”，而是“每次写都不一样”。这时候就需要一套统一的模板来约束。

3.1 顺序查找：什么时候够用

顺序查找就是最朴素的“从头到尾找一遍”，时间复杂度 O(n)。它的优点是：不要求数据有序，不占用额外空间，实现一秒就能写出来。缺点是：数据量大时性能不行。

javascript复制function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

这个模板看起来简单，但我必须提醒一点：返回值的语义要先定好。 是返回下标，还是返回布尔值，还是返回目标元素本身？如果找不到，返回 -1 还是 null？我在实际代码里见过因为返回值语义不统一，导致上层判断逻辑混乱的案例。

顺序查找适合小数据集。如果数据量超过一万，并且需要频繁查找，建议先排序再二分，或者直接用哈希表。这个判断标准，是我在实际项目中总结出来的经验线。

3.2 经典二分查找模板：左闭右闭

二分查找的写法五花八门，但核心就一句话：每次把搜索区间砍掉一半。 问题在于，这个“区间”到底怎么定义，是左闭右闭还是左闭右开，直接影响了循环条件和边界更新方式。

我推荐的默认模板是左闭右闭，也就是搜索范围是 [left, right]。这种写法最直观，和大多数人第一次学二分时的认知一致，也最容易记忆。

javascript复制function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

这里有几个固定的细节，每个都值得单独说明：

• while (left <= right)：因为是左闭右闭，所以当 left === right 时，区间里还有一个元素需要检查，不能退出。
• mid = left + Math.floor((right - left) / 2)：用减法代替加法，防止 left + right 溢出。这个写法在 JavaScript 里问题不大，但在 C++ 和 Java 里是经典大坑。
• 更新区间时，left = mid + 1 和 right = mid - 1：因为 mid 已经检查过了，所以必须跳过它。我见过有人在这里写 left = mid，结果造成死循环，这是最常见的二分 bug 之一。

这套模板一旦定下来，我几乎所有二分场景都会先往这个框架里套。套不进去的再单独处理。

3.3 二分查找变体模板：左边界和右边界

面试和实际业务里，标准二分（找等于 target 的元素）其实只是一半的需求，另一半需求是找边界。比如：“第一个大于等于 target 的下标”“最后一个小于等于 target 的下标”。这些可以基于标准二分改写，但如果你临时推导，很容易出错。

我常用的左边界模板返回的是“第一个大于等于 target 的下标”：

javascript复制function lowerBound(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

右边界模板返回的是“第一个大于 target 的下标”：

javascript复制function upperBound(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

这两个模板的共同点是：右边界初始值设为 nums.length，循环条件是 left < right，更新时 right = mid 而不是 mid - 1。 这套写法对应的是“左闭右开”区间，和标准二分不太一样。我平时会把标准二分和边界二分分开记忆，因为它们的边界语义不同，混在一起用最容易出问题。

用这两个模板，可以组合出很多操作。比如求“某个数的出现区间”，就是 lowerBound 和 upperBound 的组合。

3.4 二分查找模板的实际使用注意

二分的模板虽然固定，但有一个前提容易被忽略：数据必须有序控制排序顺序和查找目标的顺序一致。

我遇到过这样一个案例：数据库里查出来的数据，按字符串排序并不是全局有序的，因为中文排序、数字字符串排序都可能不符合预期。前端拿到的数据以为自己有序了，结果二分查找直接返回错误结果。排查了半天，发现是排序比较器没有和查找逻辑对齐。

所以我在模板旁边总会加一行注释：// 使用本模板前，请确保 nums 已按升序排列，且排序比较器与查找语义一致。 这行注释已经帮我挡掉了不知道多少潜在 bug。

另外一个实用技巧是：如果你要查找的目标是对象数组里的某个字段，不要直接二分对象数组。可以先提取出该字段的数组再查找，也可以传入自定义比较函数。我个人倾向于后者，因为省一次遍历，但前提是你要保证模板的写法支持传比较器。如果模板不支持，宁可多花点空间，也不要强行改写查找逻辑。

4. 排序与查找组合的真实场景：别只停留在刷题

排序和查找很少单独出现。我在实际开发里遇到最多的问题，都是“排序 + 查找”组合问题：求 Top K、区间合并、有序去重、两数之和、归并区间等等。这些场景如果能有一套模板支撑，会省很多事。

4.1 Top K 问题：排序和堆的复杂度账

Top K 问题的经典问法是“从一个很大的数组里找出最大的 K 个数”。最直观的做法是先排序再取前 K 个，时间复杂度 O(n log n)。但面试官通常会追问：能不能更快？

答案是：用堆维护大小为 K 的小顶堆，遍历数组，每次和堆顶比较，如果比堆顶大就替换并调整堆。时间复杂度是 O(n log K)。当 K 远小于 n 时，这个优化非常明显。

javascript复制// 找前 K 个最大的元素：小顶堆 + 遍历
function findTopK(nums, k) {
    if (k <= 0) return [];
    if (k >= nums.length) return nums.slice().sort((a, b) => a - b);

    const minHeap = nums.slice(0, k);
    // 建堆
    for (let i = Math.floor(k / 2) - 1; i >= 0; i--) {
        heapifyDown(minHeap, i, k);
    }

    for (let i = k; i < nums.length; i++) {
        if (nums[i] > minHeap[0]) {
            minHeap[0] = nums[i];
            heapifyDown(minHeap, 0, k);
        }
    }

    return minHeap;
}

function heapifyDown(arr, i, size) {
    while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;

        if (left < size && arr[left] < arr[smallest]) smallest = left;
        if (right < size && arr[right] < arr[smallest]) smallest = right;

        if (smallest === i) break;

        [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
        i = smallest;
    }
}

很多人以为“排序再取前 K”更简单，就没多想直接用了。其实大多数情况下没问题，但一旦数据量大，两者的差距会非常明显。我常用的判断标准是：K 小于 n / 10 时，堆方案稳赚不赔；K 接近 n 时，排序方案反而更简单高效。

如果你不想手写堆，JavaScript 里的 Array.sort 在 K 接近 n 的场景下其实完全够用。但如果你想进大厂，或者工作中要处理数据流，堆模板还是值得掌握的。

4.2 区间合并与有序去重：排序后相邻处理

区间合并（merge intervals）是很典型的“先排序后线性扫描”问题。思路是：先把区间按起点排序，然后遍历，能合并就合并，不能合并就开新区间。

javascript复制function mergeIntervals(intervals) {
    if (intervals.length <= 1) return intervals;

    // 先按起点升序排序
    intervals.sort((a, b) => a[0] - b[0]);

    const result = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = result[result.length - 1];
        const current = intervals[i];

        if (current[0] <= last[1]) {
            // 重叠，合并
            last[1] = Math.max(last[1], current[1]);
        } else {
            result.push(current);
        }
    }

    return result;
}

这里的核心逻辑是：排序把无序的区间变成了“起点有序”的序列，于是“判断是否重叠”就只需要和当前结果里的最后一个区间比较，而不需要和所有区间比较。

有序去重也是一样的逻辑：先排序，然后相邻元素比较，跳过重复项。这种方法比用 Set 去重慢，但好处是能保留排序后的顺序，而且如果还要统计每个元素的计数，排序就比哈希更好用。

这些组合题的套路都很固定：排序负责把数据变成有序，查找或扫描负责利用有序性做快速判断。 理解了这一步，你就能从“背题”升级到“套模板”。

4.3 数据库 JOIN、前端表头排序里的“排序查找”影子

回到我实际工作的场景里，排序查找模板的影子随处可见，只是很多人没意识到。

数据库里 ORDER BY 是排序，WHERE id = 5 如果走索引就是查找。数据库的索引本质上是一个排序好的数据结构（B+ 树），通过它查找数据的时间复杂度接近 O(log n)。这不就是二分查找的思想吗？只是底层实现变成了多叉树而已。

前端表格点击表头排序，看起来是 UI 交互，但底层也是排序。这里有一个细节：如果需要多列排序（比如先按日期排，日期相同再按金额排），那么排序稳定性就很关键。如果底层排序不稳定，第二列的排序结果可能会被第一列打乱。这就是为什么我前面强调“归并排序的好处是稳定”，在真实业务里它是有明确价值的。

还有日志分析里的“查找设备 IP”“查找某个字符串在某文件中的位置”，本质上也是查找算法。用不用模板取决于数据量和频率，但理解原理之后，至少不会出现“数据量大到内存都放不下，还在用顺序查找”这种低级悲剧。

5. 模板也会迭代：什么时候跳出排序查找模板

最后聊一个很多人容易忽略的问题：模板不是一成不变的。随着语言特性、数据规模、业务需求的变化，你需要的模板也应该演进。

5.1 哈希查找与映射表：O(1) 的诱惑

如果数据是无序的，但你需要频繁按值查找，二分查找并不是最优解。更简单的做法是建立一个哈希表（对象、Map、字典），把“值”映射到“位置”或“次数”。查找复杂度直接降到平均 O(1)。

我在很多项目里看到过这样的场景：一个数组反复被查找，每次都先排序再二分。看起来很高级，但实际上一次哈希表构建，后续每次查找都是 O(1)，整体收益可能比排序加二分还要高。

javascript复制function buildLookup(arr) {
    const map = new Map();
    for (let i = 0; i < arr.length; i++) {
        if (!map.has(arr[i])) {
            map.set(arr[i], []);
        }
        map.get(arr[i]).push(i);
    }
    return map;
}

用 Map 而不是普通对象的原因有三个：Map 的键可以是非字符串类型；Map 的插入顺序有保证；Map 的 has 和 get 方法语义更清晰，不会和对象的原型属性冲突。

所以我的建议是：排序查找模板主要解决“有序数据”的查找问题；如果数据本身无序且查询频率高，优先考虑哈希表。 不要抱着二分模板不放，适合的才是对的。

5.2 内置 sort 与手写排序的选择标准

手写排序模板不是让你在生产环境里禁用 Array.prototype.sort。恰恰相反，我的选择标准是：能内置就内置，内置解决不了再手写。

哪些情况内置解决不了？一是需要稳定排序但语言内置不稳定；二是需要自定义排序规则且内置 API 不好表达；三是学习场景，为了理解底层机制必须手写；四是某些极端性能要求下，内置排序可能不适合当前数据分布，需要手动调参。

我记得有一次做一个超大数据量的外部排序，数据量远超内存，不能一次性载入数组。这种情况下，Array.sort 根本没法用，只能自己写归并排序的外排序版本，把数据分块排序后再多路归并。那一刻我才真正体会到，手写排序模板不是纸上谈兵。

5.3 我迭代模板时的两个固定原则

第一个原则：模板必须附带一个最小的可运行示例。 我经常发现，三个月后重新看自己写的模板，如果只有一个函数定义，根本想不起来它是干嘛的。但只要配套一个输入输出示例和复杂度说明，大脑立刻就能恢复记忆。

第二个原则：模板的边界行为必须明确。 比如找不到元素返回什么，空数组怎么办，单元素数组怎么办，重复元素怎么办。我会在每个模板的开头用注释写清楚这些约定。这样模板之间可以无缝对接，不用每次调用时重新猜测行为。

这两个原则看起来很笨拙，但恰恰是它们让我的模板库维持了长期可用性。如果你也打算积累一套自己的排序查找模板，我建议把这两条原则也刻在脑门上。模板真正的价值不在于“写得漂亮”，而在于“反复能用”。

我自己平时验证模板的方式也很简单：准备一组随机数，包含空数组、单元素数组、全相同数组、已排序数组、逆序数组，每个模板跑一遍，看结果是否符合预期。这套最小测试用例我保存了好几年，每次写完新模板都会重新跑一遍，确保没有边角情况被遗漏。

排序查找看起来是算法里最入门的内容，但越是基础的东西，越值得花时间打磨成可以随手调用的模板。这份打磨的功夫，在我过去的笔试、面试和项目开发里，回报率高得惊人。希望这套模板框架也能在你的实践中派上用场。