javaScript实现归并排序

归并排序是一个O(nlogn)的算法，其基本思想就是一个分治的策略，先进行划分，然后再进行合并，下面举个例子。有这样一组数据：

   {5,4,1,22,12,32,45,21}

  如果对它进行归并排序的话，首先将它从中间分开，这样，它就被分成了两个数组：

   {5,4,1,22}与 {12,32,45,21}

  对这两个数组，也分别进行这样的操作，逐步的划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。

划分的过程如下图所示：

  接下来，我们进行归并操作，依照上图，划分过程是从上到下进行的，而归并的过程是从下往上进行的，例如上图中,最下层{5},{4}这两个数组，如果按升序排列，将他们合并后的数组就是{4,5}。{1}，{22}这两个子数组合并后是{1,22}。而{4,5}与{1,22}，这两个数组同属一个分支，他们也需要进行合并，由于这两个子数组本身就是有序的，所以合并的过程就是，每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，前面两个数组合并后就是{1,4,5,22}。依次类推，直到合并到最上层结束，这是数据的排序已经完成了。

归并的过程如下图所示。这个过程是从下往上的。


   它是一个在效率上高于一般排序的算法.一般排序:冒泡, 插入, 选择排序的时间复杂度为O(N^2), 而归并排序的时间复杂度为O(N*LOG N)，如果N(及排序项的数目)是10000.那么N^2就是100000000, 而N * LOG N则是40000. 也就是如果这个数量的数据.如果用归并排序需要40S的时间,那么用插入排序则需要28个小时.

归并排序算法的核心:

   核心思想就是分治算法.先进行划分,再进行排序归并.归并两个有序的数组.即归并两个有序的数组A和B,然后就有了包含这两个新数组的数组C.

  即一次拿出A和B的数组项进行比较.小的就插入到新容器C中.直到一方已经插入完毕.如果另一方还有剩余那么就表示剩余的是有序的而且比较大的.那么就直接连接到C数组容易的后面即可.

代码:
<script>

/* 排序并合并*/
function merge(left, right) {
   var re = [];
   while(left.length > 0 && right.length > 0) {
       if(left[0] < right[0]) {
           re.push(left.shift());
       } else {
           re.push(right.shift());
       }
   }
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
   return re.concat(left).concat(right);
}
 
function mergeSort(array) {
   if(array.length == 1) return array;
   /* 首先将无序数组划分为两个数组 */
   var mid = Math.floor(array.length / 2);
   var left = array.slice(0, mid);
   var right = array.slice(mid);
   /* 递归分别对左右两部分数组进行排序合并 */
   return merge(mergeSort(left), mergeSort(right));
}
var a = [23, 47 ,81 ,95 ,7, 14, 39, 55, 62, 74]
alert(mergeSort(a));