这篇文章主要介绍了关于js实现归并排序，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
递归的内存堆栈分析
一直对递归理解不深，原因是递归的过程很抽象，分析不清内存堆栈的返回过程。偶然google到一篇博文递归(不得不说，技术问题还是要多google)，对递归过程的内存堆栈分析豁然开朗，下面先列出分析过程：
// A C++ program to demonstrate working of recursion#includeusing namespace std;void printFun(int test){ if (test < 1) return; else { cout << test << " "; printFun(test-1); // statement 2 cout << test << " "; return; }}int main(){ int test = 3; printFun(test);}
登录后复制
下面这个图准确的列出了整个递归的过程，以后遇到单次递归问题，完全可以用此方法分析（对于多次递归情况，尝试画了一下归并排序里的两次递归，实在没有办法整洁的排版，作罢。。）
![4021399676-5b3d91bed0ad6_articlex[1].jpg](http://cdn.chuangxiangniao.com/2025/03/20250309060543984.jpg "https://cdn.chuangxiangniao.com/2025/03/20250309060543984.jpg")
![4021399676-5b3d91bed0ad6_articlex[1].jpg](https://cdn.chuangxiangniao.com/2025/03/20250309060543984.jpg "https://cdn.chuangxiangniao.com/2025/03/20250309060543984.jpg")
言归正传，下面分析归并排序。
归并排序
归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小，下面是图解：
![1679669172-5b3d91d862008_articlex[1].png](http://cdn.chuangxiangniao.com/2025/03/20250309140547466.png "https://cdn.chuangxiangniao.com/2025/03/20250309140547466.png")
![1679669172-5b3d91d862008_articlex[1].png](https://cdn.chuangxiangniao.com/2025/03/20250309140547466.png "https://cdn.chuangxiangniao.com/2025/03/20250309140547466.png")
观察下“治”的过程，可以看出，“治”实际上是将已经有序的数组合并为更大的有序数组。那么怎样将已经有序的数组合并为更大的有序数组？很简单，创建一个临时数组C，比较A[0]，B[0]，将较小值放到C[0]，再比较A[1]与B[0]（或者A[0]，B[1]），将较小值放到C[1]，直到对A，B都遍历一遍。可以看出数组A，B都只需遍历一遍，所以对两个有序数组的排序的时间复杂度为O(n)。
而“分”就是将原始数组逐次二分，直到每个数组只剩一个元素，一个元素的数组自然是有序的，所以就可以开始“治”的过程了。
时间复杂度分析：分的过程需要三步：log8 = 3，而每一步都需要遍历一次8个元素，所以8个元素共需要运行 8log8)次指令，那么对于 n 个元素，时间复杂度为 O(nlogn)。
代码中运用了两次递归，十分抽象难懂，画了一整页堆栈调用图，才弄明白（太凌乱就不贴了），大家可以试试。
// 融合两个有序数组，这里实际上是将数组 arr 分为两个数组function mergeArray(arr, first, mid, last, temp) { let i = first; let m = mid; let j = mid+1; let n = last; let k = 0; while(i<=m && j<=n) { if(arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while(i<=m) { temp[k++] = arr[i++]; } while(j<=n) { temp[k++] = arr[j++]; } for(let l=0; l<k; l++) { arr[first+l] = temp[l]; } return arr;}// 递归实现归并排序function mergeSort(arr, first, last, temp) { if(first<last) { let mid = Math.floor((first+last)/2); mergeSort(arr, first, mid, temp); // 左子数组有序 mergeSort(arr, mid+1, last, temp); // 右子数组有序 arr = mergeArray(arr, first, mid, last, temp); } return arr;}// examplelet arr = [10, 3, 1, 5, 11, 2, 0, 6, 3];let temp = new Array();let SortedArr = mergeSort(arr, 0 ,arr.length-1, temp);alert(SortedArr);
登录后复制
以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！
相关推荐：
JS实现希尔排序
Jquery添加loading过渡遮罩
以上就是JS实现归并排序的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2746913.html
