排序算法8--归并排序

归并排序

先将序列分成左右两部分的单独的一个个序列，然后再将分开好左右两部分单独的序列合并

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

若将两个有序表合并成一个有序表，称为2-路归并。

 举例说明归并排序的过程：

看下面归并排序的两种排序过程

 1.待排序列(14,12,15,13,11,16)

假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。

                                 先"分割"再"合并"

从上图可以看出，我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

js实现：

/* 排序并合并*/
function merge(left, right) {
   var re = [];
   while(left.length > 0 && right.length > 0) {
       if(left[0] < right[0]) {
//         shift();将数组第一个元素删除并返回第一个元素,即是拿到第一个元素
           re.push(left.shift());
       } else {
           re.push(right.shift());
       }
   }
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
   return re.concat(left,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 = new Array(7,2,6,5,1,4,3);
result=mergeSort(a);
document.write("_7归并排序"+result+"<br />");