JS实现归并排序

bluesky 发布于2019-08-22 18:31 / 2373人阅读

摘要：言归正传，下面分析归并排序。融合两个有序数组，这里实际上是将数组分为两个数组递归实现归并排序左子数组有序右子数组有序

递归的内存堆栈分析

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

// A C++ program to demonstrate working of recursion
#include
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);
}

下面这个图准确的列出了整个递归的过程，以后遇到单次递归问题，完全可以用此方法分析（对于多次递归情况，尝试画了一下归并排序里的两次递归，实在没有办法整洁的排版，作罢。。）

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

归并排序

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

观察下“治”的过程，可以看出，“治”实际上是将已经有序的数组合并为更大的有序数组。那么怎样将已经有序的数组合并为更大的有序数组？很简单，创建一个临时数组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

GPU云服务器云服务器 js 归并排序归并排序二路归并排序归并排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95947.html

js归并排序算法的原理及简单demo

摘要：最近看了一道如何给阿里两万多名员工按照年龄排序的面试题后，很想记录下来自己的解题思路，下面综合考虑到基数较大和稳定性，我们采取归并排序的算法归并算法分为两个两个灵魂步骤，即拆分归并我们先把两万多名员工的基数缩小至六名员工的基数，他们的年龄数最近看了一道如何给阿里两万多名员工按照年龄排序的面试题后，很想记录下来自己的解题思路，下面：综合考虑到基数较大和稳定性，我们采取归并排序的算法；归...

TigerChain 2019-08-23 17:16 评论0 收藏0
ts/js归并排序实现（稳定排序）

摘要：稳定排序稳定排序是指，如果原数组中有多个元素是相等的，那么这些元素在排序后数组的相对顺序应该保持不变。实现归并排序稳定排序。的参数必须为数组排序范围顺序已经正确归并排序稳定排序。稳定排序稳定排序是指，如果原数组中有多个元素是相等的，那么这些元素在排序后数组的相对顺序应该保持不变。比如：我们对{name:string, age:number}[]数组用age进行排序，有很多人是25岁...

vvpvvp 2019-08-22 16:30 评论0 收藏0
js算法-归并排序（merge_sort）

摘要：归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。若将两个有序表合并成一个有序表，称为二路归并。归并排序归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是。归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并...

stormjun 2019-08-23 14:37 评论0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。插入排序最好情况下时间复杂度是，其他情况下也都是。代码演示插入排序归并排序原生里面的方法，在里面是用归并排序实现的，而在里面是用快速排序的变体来实现的。 1、冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。假设一共有n项，那么一共需要n-1趟，第一趟需要交换n-1次，但是第一趟结束后，最后一项基本确定就...

notebin 2019-08-01 15:39 评论0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。插入排序最好情况下时间复杂度是，其他情况下也都是。代码演示插入排序归并排序原生里面的方法，在里面是用归并排序实现的，而在里面是用快速排序的变体来实现的。 1、冒泡排序冒泡算法是比较相邻的两项，如果前者比后者大，就交换他们。假设一共有n项，那么一共需要n-1趟，第一趟需要交换n-1次，但是第一趟结束后，最后一项基本确定就...

sihai 2019-08-20 10:37 评论0 收藏0