js 归并算法(递归和非递归)

怼烎@ 2023-02-19 07:27 164阅读 0赞

归并算法时间复杂度是：O(nlogn)

归并递归算法

function merge(left, right)\{  
    var result=\[\];  
    while(left.length>0 && right.length>0)\{  
        if(left\[0\]<right\[0\])\{  
        /\*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。\*/  
            result.push(left.shift());  
        \}else\{  
            result.push(right.shift());  
        \}  
    \}  
    return result.concat(left).concat(right);  
\}  
function mergeSort(items)\{  
    if(items.length == 1)\{  
        return items;  
\}  
var middle = Math.floor(items.length/2),  
    left = items.slice(0, middle),  
    right = items.slice(middle);  
    return merge(mergeSort(left), mergeSort(right));  
\}  
归并非递归算法 （javaScript）  
function mergePass(arr = \[\], temp = new Array(arr.length), N = arr.length, length = 1)\{ // 将每个元素看作是相邻的数组长度为1。  
  let t; // 迭代深度。  
  for (t = 0; Math.pow(2,t) < N; t++, length \*= 2) \{ // 每次跳过的长度翻倍。  
    const even = t%2 === 0; // 复用 arr 和 temp 来回赋值。  
    for (let left = 0;  left < N; left += 2 \* length) \{ // 左边数组起始位置 left 从0开始。  
      const middle = left + length < N ? left + length : left; // 右边数组起始位置 middle 就是left + 一个数组长度length 但是不要超过 N 。  
      const right = left + (2 \* length) < N ? left + (2 \* length) : N; // 右边界 right 就是 left + 两个数组长度。  
      merge(even ? arr : temp, even ? temp : arr, left, middle, right); // 合并每两个相邻的数组。  
    \}  
  \}  
  if(t % 2 === 0)\{  
        return arr;//返回arr  
    \}  
  return temp; // 返回 temp 。  
\}  
function merge(arr, temp, left, middle, right)\{  
  const leftEnd = middle - 1; // 通过右边数组的起始位置得到左边数组的结束位置。  
  while (left <= leftEnd && middle < right) \{ // 如果‘指针’没有越界。  
    if (arr\[left\] > arr\[middle\]) \{ // 如果左边数组第一个元素比右边数组第一个元素大。  
      temp\[left + middle - leftEnd -1\] = arr\[middle++\]; // 将右边数组最小的放入有序数组 temp（初始值为空)。  
    \} else \{  
      temp\[left + middle - leftEnd -1\] = arr\[left++\]; // 将左边数组最小的放入有序数组 temp（初始值为空)。  
    \}  
  \}  
  while(left > leftEnd && middle < right)\{ // 如果左边数组放完了，右边数组还有元素。  
    temp\[left + middle - leftEnd -1\] = arr\[middle++\]; // 那么依次将右边数组剩余的元素放入 temp 。  
  \}  
  while(left <= leftEnd && middle >= right)\{ // 如果右边数组放完了，左边数组还有元素  
    temp\[left + middle - leftEnd -1\] = arr\[left++\]; // 那么依次将左边数组剩余的元素放入 temp 。  
  \}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序的递归与非递归实现

文章目录归并排序 1. 基本思想 2.归并排序的递归实现 2.1 原理 2.2 代码实现

浅浅的花香味﹌/ 2024年03月27日 15:13/ 0 赞/ 217 阅读

相关归并排序(递归和非递归)

归并排序一.递归二.非递归 1.基础 2.改进一.递归 > 归并实际上就是把一个数组每次二分，分别排序每个子数组再将有

ゝ一纸荒年。/ 2024年03月24日 17:10/ 0 赞/ 208 阅读

相关 js递归(js递归算法)

递归论的基本内容有哪些呢？任给m,n的值，如果m为0，可由第一式算出；如果m不为0而n为0，可由第二式化归为求g(m,1)的值，这时第一变目减少了；如果m，n均不为0,

超、凢脫俗/ 2023年10月11日 18:48/ 0 赞/ 194 阅读

相关 java实现堆排序、冒泡排序、快速排序（递归和非递归）、归并排序（递归与非递归）

堆排序和直接选择排序很像，每次去一个最大值，放到数组的最后。实现：1. 先针对整个数组建堆；2.循环取堆顶最大值，放到最后面 3调整堆时间复杂度O(Nl

快来打我*/ 2023年06月16日 04:52/ 0 赞/ 30 阅读

相关 js 归并算法(递归和非递归)

归并算法时间复杂度是：O(nlogn) 归并递归算法 function merge(left, right)\{ var result=\[\

怼烎@/ 2023年02月19日 07:27/ 0 赞/ 165 阅读

相关 280-归并排序算法(递归和非递归)

归并排序算法(递归和非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

深碍√TFBOYSˉ_/ 2023年01月14日 13:57/ 0 赞/ 283 阅读

相关归并排序（递归和非递归法）

本文主要参考两篇博文：递归法归并排序函数代码来自： [http://blog.csdn.net/morewindows/article/details/6678165

╰半橙微兮°/ 2022年08月01日 12:28/ 0 赞/ 359 阅读

相关二分查找（非递归算法和递归算法）

非递归算法： package mytest; public class test { public static int Bina

水深无声/ 2022年05月29日 06:17/ 0 赞/ 409 阅读

相关归并排序（递归和非递归）

学习之后，自己练习手写一下排序算法，加深印象原理：假设初始序列含有n个记录，则可以看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的子序

水深无声/ 2022年05月28日 01:44/ 0 赞/ 390 阅读

相关归并算法的非递归实现

根据归并算法的实现原理我们得知:每次分组时组内元素个数上限都是2的幂次方我们可以令步长step的初值为2,然后将数组中每step个元素作为一组,将其内部进行排序,(将左st

矫情吗；*/ 2022年03月26日 10:24/ 0 赞/ 309 阅读