归并排序

计算机算法设计分析可以说是进入到复习阶段了，当然也可以说成是自习阶段，归并排序已经学过有一段时间了。学习的时候没有坚持写笔记，后来挺痛苦的，看来还是要养成做总结的好习惯。同志们一起复习总结哟！
现在聊聊归并排序吧。

• 首先，假如有两个有序的数组，我们要让它合并成一个有序的数组，应该如何处理呢？
  代码如下：

void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
  
    i = j = k = 0;  
    while (i < n && j < m)  
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  
    while (i < n)  
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
} 

以上是借助了第三个数组，那么，如果将一个无序的数组进行排序，就可以将这个数组分成两部分，使每部分都有序，然后再进行排序与合并，就可以实现整体有序。

• 具体代码，表示使用JS写的，不过是按照c语言思想表达出来的，没有借助与js函数，主要是体现思想，有兴趣的话，可以用java/c等同样表达出来。

function sortIt(s,first,mid,last,temp) {
    let i = first;
    let j = mid + 1;
    let m = mid;
    let n = last;
    let k = 0;
    while (i <= m && j <= n){
        if(s[i] < s[j]) {
            temp[k++] = s[i++];
        }
        else temp[k++] = s[j++];
    }
    while (i <= m){
        temp[k++] = s[i++];
    }
    while (j <= n) {
        temp[k++] = s[j++];
    }
    for(i = 0; i < k; i++)
    {
        a[i+first] = temp[i];//将排好顺序的部分放在数组a中
    }
}
function mergeSort(a,first,last,temp) {
    if(first < last) {

        let mid =parseInt((first + last) / 2) ;　//转化为int型
        mergeSort(a,first,mid,temp);　//使左边有序
        mergeSort(a,mid + 1, last,temp);//使右边有序
        sortIt(a,first,mid,last,temp);//合并两个有序的
    }
}
let a = [5,3,1,9,8,2,4];
let  temp = [];
mergeSort(a,0,a.length-1,temp);
console.log(a);

可以动手走一下过程，会有很大的收获。