JavaScript排序算法之归并排序

偏执的太偏执、 2022-07-28 01:03 214阅读 0赞

**归并排序的引入**

**             归并排序的命名来自它的实现原理： 把一系列排好序的子序列合并成一个大的完整有序序列。 从理论上讲， 这个算法很容易实现。 我们需要两个排好序的子数组， 然后通过比较数据大小， 先从最小的数据开始插入， 最后合并得到第三个数组。 然而， 在实际情况中， 归并排序还有一些问题， 当我们用这个算法对一个很大的数据集进行排序时， 我们需要相当大的空间来合并存储两个子数组。 就现在来讲， 内存不那么昂贵， 空间不是问题， 因此值得我们去实现一下归并排序， 比较它和其他排序算法的执行效率。**

自底向上的排序方法

采用非递归或者迭代版本的归并排序是一个自底向上的过程。 这个算法首先将数据集分解为一组只有一个元素的数组。 然后通过创建一组左右子数组将它们慢慢合并起来， 每次合并都保存一部分排好序的数据， 直到最后剩下的这个数组所有的数据都已完美排序。 下图演示了自底向上的归并排序算法如何运行的。

![Image 1][]

代码测试：

1.所调用的函数：

**function CArray**(numElements) \{  
   this.dataStore = \[\];  
   this.toString = toString;

this.numElements = numElements;

this.setData = setData;                 //随机生成一组数  
   this.mergeSort=mergeSort;  
   this.mergeArrays=mergeArrays;  
   for (var i = 0; i < numElements; ++i) \{  
      this.dataStore\[i\] = i;  
   \}  
\}

**function setData() \{**   
   for (var i = 0; i < this.numElements; ++i) \{  
      this.dataStore\[i\] = Math.floor(Math.random() \*  
                          (this.numElements+1));  
   \}  
\}

function toString() \{   
   var retstr = "";  
   for (var i = 0; i < this.dataStore.length; ++i) \{  
      retstr += this.dataStore\[i\] + " ";  
      if (i > 0 && i % 10 == 0) \{  
         retstr += "\\n";  
      \}  
   \}  
   return retstr;  
\}  
**function mergeSort()** \{  
        if (this.dataStore.length < 2) \{  
        return;  
        \}  
        var step = 1;  
        var left, right;  
        while (step < this.dataStore.length) \{  
        left = 0;  
        right = step;  
        while (right + step <= this.dataStore.length) \{  
        mergeArrays(this.dataStore, left, left+step, right, right+step);  
        left = right + step;  
        right = left + step;  
        \}  
        if (right < this.dataStore.length) \{  
        mergeArrays(this.dataStore, left, left+step, right, this.dataStore.length);  
        \}  
        step \*= 2;  
    \}  
\}  
  
**function mergeArrays**(arr,startLeft, stopLeft, startRight, stopRight) \{  
        var rightArr = new Array(stopRight - startRight + 1);  
        var leftArr = new Array(stopLeft - startLeft + 1);  
        k = startRight;  
        for (var i = 0; i < (rightArr.length-1); ++i) \{  
        rightArr\[i\] = arr\[k\];  
        ++k;  
        \} k  
        = startLeft;  
        for (var i = 0; i < (leftArr.length-1); ++i) \{  
        leftArr\[i\] = arr\[k\];  
        ++k;  
        \}  
        rightArr\[rightArr.length-1\] = Infinity; // 哨兵值  
        leftArr\[leftArr.length-1\] = Infinity; // 哨兵值  
        var m = 0;  
        var n = 0;  
        for (var k = startLeft; k < stopRight; ++k) \{  
        if (leftArr\[m\] <= rightArr\[n\]) \{  
        arr\[k\] = leftArr\[m\];  
        m++;  
        \}  
        else \{  
        arr\[k\] = rightArr\[n\];  
        n++;  
        \}  
        \}  
        alert("left array - ", leftArr\[m\]);  
        alert("right array - ", rightArr\[n\]);  
        \}  
  
**说明：**函数中的关键点就是  step  这个变量， 它用来控制  mergeArrays()  函数生成的leftArr  和  rightArr  这两个子序列的大小。 通过控制子序列的大小， 处理排序是比较高效的， 因为它在对小数组进行排序时不需要花费太多时间。 合并之所以高效， 还有一个原因， 由于未合并的数据已经是排好序的， 将它们合并到一个有序数组的过程非常容易  
**测试**

var nums = new CArray(10);  
nums.setData();  
alert(nums.toString());  
nums.mergeSort();  
alert(nums.toString());

[Image 1]:

发表评论取消回复

表情：

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

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

相关阅读

相关排序算法之归并排序

> 归并排序 > \ 数组分为左右两个子数组，按序依次比较子数组中每个元素大小，将小的元素放入新的临时数组中。 > 时间复杂度O(nlog2n); > 空

古城微笑少年丶/ 2022年11月02日 13:28/ 0 赞/ 191 阅读

相关排序算法之归并排序

先看一下下面这张图 ![Center][] 下面分析归并排序：归并排序把数组划分成几个小数组，然后小数组成划分，直到每个数组都只有一个元素，然后将相邻的两个数组进

ゞ浴缸里的玫瑰/ 2022年09月25日 15:27/ 0 赞/ 201 阅读

相关 JavaScript排序算法之归并排序

归并排序的引入归并排序的命名来自它的实现原理：把一系列排好序的子序列合并成一个大的完整有序序列。从理论上讲，这个算法很容易实现。我们需要两

偏执的太偏执、/ 2022年07月28日 01:03/ 0 赞/ 215 阅读

相关排序算法之归并排序

归并排序> 之前曾经实现过堆排序，它用到了完全二叉树，但是堆的设计本身就是比较复杂的，而今天要实现的归并排序同样的也用到了完全二叉树的思想，这种思想比堆排序较为简单.

蔚落/ 2022年07月14日 05:20/ 0 赞/ 259 阅读

相关排序算法之归并排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

你的名字/ 2022年06月16日 09:27/ 0 赞/ 230 阅读

相关算法排序算法之归并排序

归并排序归并排序主要是二路归并排序基本思想设数组a中存放了n个数据元素初始时把它们看成n个长度为1的有序子数组，然后从第一个子数组开始，把相邻

拼搏现实的明天。/ 2022年06月15日 12:56/ 0 赞/ 271 阅读

相关 C++排序算法之归并排序

归并排序（1）算法介绍归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用，归并排序将两个已经有序的序列合并成一个有序的序

阳光穿透心脏的1/2处/ 2022年06月12日 02:42/ 0 赞/ 239 阅读

相关 JavaScript经典排序算法——归并排序

“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到\[n/2\]（向上

柔情只为你懂/ 2022年05月26日 12:10/ 0 赞/ 236 阅读

相关排序算法之归并排序

归并排序（MERGE-SORT）建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并

Love The Way You Lie/ 2022年04月16日 05:08/ 0 赞/ 250 阅读

相关排序算法之归并排序

归并排序是利用递归与分治思想将数据序列划分成越来越小的半子序列，在对其进行排序，最后利用递归将排好序的半子序列合并成越来越大的有序序列。归并排序中，归即是递归的意思，即递

旧城等待，/ 2021年09月18日 04:24/ 0 赞/ 408 阅读