当前位置:Gxlcms > JavaScript > JS实现归并排序

JS实现归并排序

时间:2021-07-01 10:21:17 帮助过:15人阅读

这篇文章主要介绍了关于JS实现归并排序,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下

递归的内存堆栈分析

一直对递归理解不深,原因是递归的过程很抽象,分析不清内存堆栈的返回过程。偶然google到一篇博文递归(不得不说,技术问题还是要多google),对递归过程的内存堆栈分析豁然开朗,下面先列出分析过程:

// A C++ program to demonstrate working of recursion
#include<bits/stdc++.h>
using 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

言归正传,下面分析归并排序。

归并排序

归并排序采用的是分治的思想,首先是“分”,将一个数组反复二分为两个小数组,直到每个数组只有一个元素;其次是“治”,从最小数组开始,两两按大小顺序合并,直到并为原始数组大小,下面是图解:

1679669172-5b3d91d862008_articlex[1].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;
}

// example
let 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实现归并排序的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行