17370845950

JavaScript排序算法需根据场景选择：小规模用冒泡（O(n²)），高效通用选快排（平均O(n log n)），稳定性要求高用归并（稳定O(n log n)）；业务中优先用原生sort，手写适用于定制逻辑、教学或性能优化。

JavaScript中实现排序算法，核心是理解算法逻辑并用数组操作和循环结构表达出来。原生的 Array.prototype.sort() 虽方便，但默认按字符串排序，处理数字常出错；手动实现则能深入掌握原理，也便于应对特殊需求（如稳定排序、自定义比较、内存限制等）。

冒泡排序：理解交换逻辑的基础

冒泡排序通过重复遍历数组，两两比较相邻元素并交换位置，使较大值逐步“浮”到末尾。它简单直观，适合教学，但时间复杂度为 O(n²)，仅适用于小规模或教学演示。

• 外层循环控制轮数（最多 n−1 轮），内层循环负责每轮的相邻比较
• 每轮后末尾元素已就位，内层循环范围可逐步缩小
• 可加入提前终止优化：若某轮无交换，说明已有序，直接退出

快速排序：兼顾效率与可读性的主流选择

快排采用分治思想：选一个基准（pivot），将数组分为小于、大于基准的两部分，再递归排序。平均时间复杂度 O(n log n)，是手写排序中最常用且易理解的高效方案。

• 基准可选首项、末项或随机索引，避免最坏情况（已排序数组选首/末作基准会退化为 O(n²)）
• 分区过程建议用双指针（左右扫描），避免额外空间开销
• 递归调用前需确保子数组长度 > 1，防止无限递归

归并排序：稳定且可预测的 O(n log n) 解法

归并排序同样分治，但策略是“先分后合”：递归将数组拆成单元素，再两两合并为有序数组。它稳定（相等元素相对位置不变）、时间复杂度稳定为 O(n log n)，适合对稳定性有要求的场景。

• 合并函数是关键：用两个指针分别遍历左右子数组，取较小值推入结果，剩余元素直接拼接
• 每次合并需新建临时数组，空间复杂度为 O(n)，不适合内存敏感环境
• 非原地排序，若需原地操作，可考虑迭代版或改用其他算法

实际使用建议：何时手写，何时用原生？

多数业务场景优先使用 arr.sort((a, b) => a - b) 处理数字排序，或 arr.sort((a, b) => a.name.localeCompare(b.name)) 处理字符串。手写排序更适合以下情况：

• 需要明确控制排序行为（比如多字段、自定义规则、稳定性保证）
• 在低性能环境做算法题、面试、教学或调试底层逻辑
• 处理特殊数据结构（如链表、流式数据）无法直接调用原生方法
• 已有性能瓶颈且 profiling 显示 sort 是热点，需定制优化（如内省排序混合策略）

不复杂但容易忽略：手写时注意边界条件（空数组、单元素、重复值）、数值比较用减法而非 （避免隐式转换错误），以及避免修改原数组除非明确要求。