【免费下载链接】javascript-algorithms JavaScript implementations of computer science algorithms项目地址https://gitcode.com/gh_mirrors/jav/javascript-algorithms点击查看免费下载本篇文章以 src/sorting/readme.md 中给出的“所有排序算法复杂度对比表”为核心骨架逐一对照 src/sorting 目录下 17 个排序算法模块的源码与 JSDoc 注释补全每种算法的复杂度依据、实现原理、稳定性与适用场景并给出可复制的调用示例与测试验证方式帮助你基于该项目快速完成排序算法的选型与实践。目录导读一、对比表全貌17 种算法的复杂度一览二、O(N log N) 级别快速排序与归并排序家族三、O(N^2) 级别经典简单排序的四种形态四、线性时间排序桶排序、计数排序与基数排序五、面向字符串的三种排序LSD、MSD 与 3-way 字符串快速排序六、通用 API 约定比较函数、导出结构与测试方式七、选型速查表一、对比表全貌17 种算法的复杂度一览原文档 src/sorting/readme.md 的核心是一张复杂度对比表列出src/sorting目录下全部 17 个排序算法文件及其标称复杂度但“When to use?”一列留空。下表完整保留原表内容并补上按源码可以确认的模块导出名见各文件末尾的exports.xxx语句Algorithm文件Complexity原文档源码模块导出名3-way-string-quicksort.jsO(N^2)quicksortbubblesort.jsO(N^2)bubbleSortbucketsort.jsO(N)bucketSortcountingsort.jsO(N)countingSortheapsort.jsO(N log N)heapSortinsertion-binary-sort.jsO(N^2)insertionBinarySortinsertionsort.jsO(N^2)insertionSortlsd.jsO(N*M)N 为键数量、M 为键的最大位数lsdmergesort.jsO(n log(n))mergeSortmsd.jsO(N*M)N 为键数量、M 为键的最大位数msdoddeven-sort.jsO(N^2)oddEvenSortquicksort-middle.jsO(N log(N))quickSortquicksort.jsO(nlog n)quickSortradixsort.jsO(N K)N 为键数量、K 为平均键长位数radixSortrecursive-insertionsort.jsO(N^2)recursiveInsertionSortselectionsort.jsO(N^2)selectionSortshellsort.jsO((nlog(n))^2)shellSort需要说明的是“When to use?”一列在原文档中为空本文后续各节将结合源码结构、注释与算法性质给出选型建议均以仓库内可确认的内容为限不夸大任何算法的绝对优势。二、O(N log N) 级别快速排序与归并排序家族这一族是通用场景下最常用的比较型排序源码注释中明确标注了各自的时间复杂度。2.1 quicksort.js基于 Lomuto 划分的经典快速排序quicksort.js 源码注释明确写明“Its complexity is O(nlog n)”。其实现要点采用Lomuto 划分源码第 40 行partition函数以子数组最后一个元素array[right - 1]作为基准pivot从left扫描到right - 1将小于基准的元素交换到左侧最后把基准放到分界位置并返回分界下标minEnd递归地对[left, p)与[p 1, right)两段继续排序源码第 63-70 行。与任何快速排序一样平均复杂度 O(N log N)、最坏情况 O(N^2)例如已有序数组且基准总是极值的情形且不稳定。它适合对内存占用敏感、期望原地排序仅交换数组元素无辅助数组的通用场景。2.2 quicksort-middle.js取中位元素为基准的 Hoare 划分quicksort-middle.js 是快速排序的变体注释明确给出“Time complexity: O(N log(N))”。与 2.1 的区别在于基准取array[Math.floor((left right) / 2)]源码第 30 行即子数组中间元素采用Hoare 划分左右双指针向中间靠拢左指针停在大于等于基准处、右指针停在小于等于基准处然后交换源码第 32-47 行递归区间为[left, mid - 1]与[mid, right]源码第 59-67 行。由于基准取中间元素可以在一定程度上规避已有序输入下的最坏情况退化是“就地、快速、通用”场景的稳妥选择。同样不稳定。2.3 quicksort-declarative.js函数式声明式快速排序quicksort-declarative.js 是快速排序的声明式函数式实现注释标注“Time complexity: O(N log(N))”。核心代码只有寥寥数行const [x, ...rest] array; return [ ...quicksort(rest.filter(v cmp(v, x) 0), cmp), x, ...quicksort(rest.filter(v cmp(v, x) 0), cmp) ];它把数组拆成首元素x与剩余部分rest用filter按比较函数分成小于与不小于x两组再递归拼接。优点是代码极其简洁、可读性强、无副作用返回新数组代价是每次递归都会创建新数组内存占用高于原地版本不适合超大数组。2.4 heapsort.js基于最大堆的原地排序heapsort.js 注释明确“Time complexity: O(N log N)”实现分三步buildMaxHeap从Math.floor(array.length / 2)开始向前对每个节点执行heapify把数组建成最大堆源码第 49-54 行循环将堆顶最大值与末尾交换缩小堆尺寸再对堆顶执行heapify恢复堆性质源码第 80-86 行heapify是比较当前节点与其左右孩子2 * index 1、2 * index 2把最大值上浮源码第 20-39 行。堆排序的特点是原地、最坏情况稳定为 O(N log N)不依赖输入分布但不稳定且实际常数较大。适合对“最坏情况性能有硬性保证”且不能接受额外内存的场景。2.5 mergesort.js基于链表的归并排序mergesort.js 是本目录中唯一一个把归并过程建立在链表src/data-structures/linked-list.js之上的实现mergeSort递归地对[start, middle)与[middle, end)两半分别排序middle Math.ceil((start end) / 2)源码第 30-43 行mergeSort.merge把左右两半分别推入两个链表然后反复取两个链表头中较小者写回原数组源码第 65-99 行。归并排序稳定、最坏与平均复杂度均为 O(N log N)代价是需要 O(N) 辅助空间此处为链表节点。适合对稳定性有要求、数据规模较大且不介意额外内存的场景。2.6 shellsort.js基于固定 gap 序列的希尔排序shellsort.js 使用固定的 gap 序列[701, 301, 132, 57, 23, 10, 4, 1]源码第 10 行对每个 gap 执行插入排序for (var k 0; k gaps.length; k 1) { gap gaps[k]; for (var i gap; i array.length; i gap) { current array[i]; for (var j i; j gap cmp(array[j - gap], current) 0; j - gap) { array[j] array[j - gap]; } array[j] current; } }原文档将其复杂度标为 O((nlog(n))^2)。希尔排序原地、不稳定但相比 O(N^2) 的简单排序在中等规模数据上有明显提升且代码量小适合对内存零额外开销的通用排序。三、O(N^2) 级别经典简单排序的四种形态3.1 bubblesort.js带提前终止优化的冒泡排序bubblesort.js 源码注释标注“Complexity: O(N^2)”。实现中有一个值得注意的优化每轮内层循环用swapCount记录交换次数若某轮没有发生任何交换说明数组已有序则直接break提前结束源码第 29-40 行。因此它对“基本有序”的输入实际表现优于最坏情况。适合教学演示与极小规模数据。3.2 insertionsort.js / recursive-insertionsort.js迭代版与递归版插入排序insertionsort.js 从i 1开始把array[i]逐一向左比较并后移元素直到找到正确插入位置源码第 30-38 行。对基本有序的数据其实际性能接近 O(N)是“几乎排好序的小数组”场景的经典选择且稳定。recursive-insertionsort.js 是同一算法的递归改写先递归处理前max - 1个元素再把array[max]插入到已排序前缀中的正确位置源码第 28-43 行。两者复杂度同为 O(N^2)源码注释一致递归版更便于理解算法结构但会引入 O(N) 的递归调用栈。3.3 insertion-binary-sort.js二分查找定位的插入排序insertion-binary-sort.js 是对插入排序的改进定位插入点时不再线性扫描而是对已排序前缀做二分查找源码第 36-47 行找到插入位置left后统一后移元素源码第 48-51 行。源码注释明确说明该优化是安全的——“二分查找只作用于数组前半部分而这一部分确实是已排序的”。注意二分查找只把比较次数从 O(N^2) 降到 O(N log N)元素移动仍是 O(N^2)因此总复杂度仍标注为 O(N^2)。适合在比较代价昂贵如对象字段比较而移动代价较低的场景且稳定。3.4 selectionsort.js交换次数最少的 O(N^2) 排序selectionsort.js 每轮扫描未排序区间用idx记录最小值下标一轮结束后只做一次交换源码第 30-40 行。其特点是交换次数恒为 O(N)远少于冒泡与插入排序适合“交换代价远高于比较代价”的场景如大对象数组。但它不稳定且对已有序数据没有提前终止的优化。3.5 oddeven-sort.js奇偶交换排序oddeven-sort.js 源码注释标注“Complexity: O(N^2)”。其思路是反复交替执行两轮相邻比较交换先比较交换所有(1,2)、(3,4)...奇数对再比较交换所有(0,1)、(2,3)...偶数对源码第 26-40 行直到某一轮完全有序sorted保持true为止。该算法与冒泡排序复杂度同级主要价值在于天然适合并行化奇数轮与偶数轮内部的相邻比较互不依赖是并行排序教学中的典型例子稳定。四、线性时间排序桶排序、计数排序与基数排序这三者均不基于比较源码注释中标注了 O(N) 或 O(N*K) 的复杂度代价是对输入类型有额外约束。4.1 countingsort.js只适用于整数的计数排序countingsort.js 源码注释明确指出“Its correct only for array of integers”且“Time complexity: O(N)”。实现分三步getCount统计每个元素出现次数以元素值本身作为下标源码第 13-21 行getLessCount前缀累加得到“小于等于每个值的元素个数”源码第 31-40 行sort按less[current]把每个元素放到最终位置并用currentPositions处理重复值源码第 50-65 行。适用前提非负整数、值域不能过大值域过大会导致计数数组巨大。当数据是密集整数如 0~1000 的分数时O(N) 的线性表现优于任何比较排序。4.2 bucketsort.js按整数部分分桶的桶排序bucketsort.js 源码注释标注“Time complexity: O(N) in case the data is with uniform distribution”数据均匀分布时为 O(N)。实现要点createBuckets以Math.floor(current)作为桶下标把每个元素放入对应桶源码第 38-49 行sortBuckets对每个桶内部用插入排序源码第 58-65 行插入排序实现见文件内第 14-27 行unionBuckets按下标顺序把各桶拼接成结果源码第 75-85 行。从源码结构可以推断该实现假设数据分布在[0, ∞)的非负浮点数区间桶下标即整数部分。数据均匀分布时每个桶内元素很少插入排序近乎线性总复杂度接近 O(N)若数据集中到少数桶则退化为桶内插入排序的 O(N^2) 行为。4.3 radixsort.jsLSD 基数排序整数版radixsort.js 源码注释明确“Worst-case time complexity is O(N K) for N keys with K being the average key length, measured in number of digits”即原文档表格中“O(N K)”的含义是K 为按位数计的平均键长。实现是经典的 LSD最低位优先基数排序关键细节字母表大小R 10十进制数字 0-9源码第 48 行getDigit用number.toString()[size - 1 - lsdOffset]取出从最低位起的第lsdOffset位数字源码第 19-28 行先求maxKeySize最大键的位数然后逐位执行统计频次 → 前缀累加cumulates→ 逆序写入辅助数组aux→ 拷回原数组源码第 54-93 行。适用于非负整数且位数差异不大的数据稳定是整数排序中兼顾速度与稳定性的代表。五、面向字符串的三种排序LSD、MSD 与 3-way 字符串快速排序5.1 lsd.js最低位优先的字符串基数排序lsd.js 源码注释标注“Time complexity: O(N*M) for N keys which have M or fewer digits”。它按字符编码charCodeAt从最后一位字符向第一位逐字符执行计数排序源码第 20-46 行。示例注释显示其输入为等长字符串数组如console.log(sort([aab, bbb, aaa, acc, bcc])); // [ aab, aaa, acc, bbb, bcc ]注意LSD 的前提是所有字符串等长或按固定长度补齐否则不同长度的字符串按字符编码排序会产生非预期结果。它是稳定排序测试用例 test/sorting/lsd.spec.js 覆盖了空数组、单元素、等长字符串等场景。5.2 msd.js最高位优先的字符串基数排序msd.js 源码注释标注“Time complexity: O(N*M)”并明确“Algorithm is stable”。与 LSD 相反它从第一位字符开始排序之后递归地对每个字符分组内部继续按下一位排序源码第 8-36 行。代码中的两个细节值得注意charCodeAt(str, i)在i超出字符串长度时返回-1源码第 4-6 行使得短字符串排在长字符串之前——这正是 MSD 能正确处理“不同长度字符串”的原因测试用例 test/sorting/msd.spec.js 专门覆盖了“differently length strings”场景每层递归前先做频次统计与前缀累加再按分组递归源码第 15-35 行。MSD 适合字典序排序如单词表、文件路径列表无需等长字符串且天然能利用“前缀相同的字符串”聚簇的特性。5.3 3-way-string-quicksort.js三向切分字符串快速排序3-way-string-quicksort.js 源码注释明确“Algorithm is NOT stable”原文档将其复杂度标为 O(N^2)最坏情况。它把快速排序的三向切分思想应用到字符串的逐字符比较上以charAt(arr[lo], d)为基准字符p源码第 22 行扫描指针i从lo 1到hi小于p的交换到lowPointer一侧大于p的交换到highPointer一侧等于p的留在中间源码第 26-38 行递归处理三段小于段、等于段p 0时按下一位d 1继续、大于段源码第 40-44 行。它是原地算法仅交换数组元素特别适合大量共享前缀的字符串集合如 URL、基因序列、IP 地址此时三向切分能显著减少比较次数。代价是不稳定且最坏 O(N^2)。六、通用 API 约定比较函数、导出结构与测试方式6.1 统一的比较函数约定从源码可以看出全部 17 个排序模块遵循统一的 API 约定默认比较函数均为function compare(a, b) { return a - b; }见 bubblesort.js、insertionsort.js、selectionsort.js 等即默认按数值升序大多数排序函数接受可选的第二个参数cmp如 heapsort.js 的heapSort(array, cmp)、quicksort-middle.js 的quickSort(array, cmp)比较函数返回值约定与Array.prototype.sort一致返回负值、零或正值分别表示a小于、等于或大于b桶排序、计数排序、基数排序、LSD、MSD、3-way 字符串快速排序、奇偶排序这 7 个模块不接受cmp参数它们依赖输入类型本身的约束整数、浮点数或字符串。所有模块都使用 UMD 风格包装(function (exports) { ... }(typeof exports undefined ? window : exports))因此既可以在 Node.js 中require也可以在浏览器端直接挂到window上使用。6.2 调用示例Node.js以归并排序为例模块注释中给出的用法如下var array [2, 4, 1, 5, 6, 7]; var mergeSort require(path-to-algorithms/src/sorting/mergesort).mergeSort; mergeSort(array); // [1, 2, 4, 5, 6, 7]传入自定义比较函数即可改变排序方向例如降序function comparator(a, b) { return b - a; } var sorted require(path-to-algorithms/src/sorting/heapsort).heapSort(array, comparator);6.3 测试验证方式仓库使用 Jasmine见 package.json 中的gulp-jasmine依赖组织测试排序测试分为两类通用测试夹具test/sorting/sort.testcase.js所有“接受cmp参数”的排序如 mergesort.spec.js、quicksort.spec.js、bubblesort.spec.js都复用该夹具覆盖空数组、已有序数组、随机数组以及传入降序比较函数四种情形专项测试LSD / MSD / 3-way 字符串快速排序有各自的专项测试如 test/sorting/lsd.spec.js 验证等长字符串排序、test/sorting/msd.spec.js 额外验证不同长度字符串场景test/sorting/bucketsort.spec.js 与 test/sorting/countingsort.spec.js 则验证空数组、元素数量不变与升序结果。运行全部测试npm install npm run test根据 package.json 的脚本定义npm run test等价于gulp test会执行所有*.spec.js文件。七、选型速查表结合上述源码事实将原文档留空的“When to use?”列补全如下算法复杂度原文档适用场景依据源码注释与实现结构quicksort.jsO(nlog n)通用原地排序、内存敏感场景最坏 O(N^2)不稳定quicksort-middle.jsO(N log(N))通用快速排序中间元素作基准可缓解已有序输入退化quicksort-declarative.jsO(N log(N))代码简洁优先、数据量适中可接受新数组开销见 quicksort-declarative.jsheapsort.jsO(N log N)需要最坏情况 O(N log N) 保证且原地排序的场景mergesort.jsO(n log(n))需要稳定排序、可接受 O(N) 辅助空间的场景链表归并见 mergesort.jsshellsort.jsO((nlog(n))^2)中等规模、零额外内存开销的通用排序bubblesort.jsO(N^2)教学演示、极小规模数据基本有序输入可提前终止见 bubblesort.jsinsertionsort.jsO(N^2)基本有序的小数组接近线性表现稳定recursive-insertionsort.jsO(N^2)与插入排序相同递归形式便于理解insertion-binary-sort.jsO(N^2)比较代价高于移动代价的场景比较次数降为 O(N log N)见 insertion-binary-sort.jsselectionsort.jsO(N^2)交换代价远高于比较代价的场景交换次数恒为 O(N)不稳定oddeven-sort.jsO(N^2)并行化相邻比较的排序教学与实验见 oddeven-sort.jscountingsort.jsO(N)非负整数、值域较小的密集数据见 countingsort.js 注释bucketsort.jsO(N)均匀分布的非负浮点数桶内插入排序见 bucketsort.js 注释radixsort.jsO(N K)非负整数、位数差异小的数据稳定K 为平均位数见 radixsort.js 注释lsd.jsO(N*M)等长字符串的稳定基数排序见 lsd.js 注释msd.jsO(N*M)不同长度字符串的字典序排序稳定见 msd.js 注释3-way-string-quicksort.jsO(N^2)大量共享前缀的字符串集合的原地排序不稳定见 3-way-string-quicksort.js 注释使用建议通用数值数组优先考虑 quicksort-middle.js 或 heapsort.js需要稳定性时选择 mergesort.js通用或 radixsort.js / countingsort.js整数字符串字典序选择 msd.js共享前缀多的字符串选择 3-way-string-quicksort.js小规模或基本有序数据选择 insertionsort.js。以上建议均基于本仓库源码注释与实现结构可确认的事实具体选型仍需结合实际数据规模与分布进行基准验证。赞分享【免费下载链接】javascript-algorithms JavaScript implementations of computer science algorithms项目地址https://gitcode.com/gh_mirrors/jav/javascript-algorithms点击查看免费下载相关推荐10种JavaScript排序算法终极性能对比从入门到精通的效率分析指南10种JavaScript排序算法终极性能对比从入门到精通的效率分析指南 在计算机科学领域排序算法是基础且核心的内容。JavaScript作为当今最流行的编示例工程yazi排序器实现多种排序算法与性能对比yazi排序器实现多种排序算法与性能对比 引言为什么文件排序如此重要 在日常文件管理操作中排序功能是用户最频繁使用的核心功能之一。一个高效、准确的排序系开发工具CLI终极C排序算法指南20种排序方法深度对比与实战应用终极C排序算法指南20种排序方法深度对比与实战应用 在计算机科学领域排序算法是数据处理的基石。GitHub加速计划中的C语言算法库gh_mirrors/示例工程上一篇3步轻松搞定B站缓存视频转换让m4s格式变通用mp4的完整指南下一篇3分钟上手免费音乐歌词批量下载神器163MusicLyrics终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
