紧接着上一篇的快速排序,本文主要来讲一下归并排序。快速排序,归并排序,以及堆排序,也就是我们排序里可能会经常用到的三种了。学会它们,也可以会不少的题目。先上Js和C的递归写法吧。

下面先上归并排序的排序过程:

归并排序

归并排序过程

JavaScript Solution

function MergeSort(data){
    if(data.length === 1)
        return data
    else{
        let middle = parseInt(data.length/2)
        let left = data.slice(0,middle)
        let right = data.slice(middle)
        return Merge(MergeSort(left), MergeSort(right))
     }
}

function Merge(left,right){
    let arr = []
    let l = 0 , r = 0
    while( l < left.length && r < right.length ){
        if( left[l] < right[r])
            arr.push(left[l++])
        else
            arr.push(right[r++])
     }

     while(l < left.length)
             arr.push(left[l++])

     while(r < right.length)
             arr.push(right[r++])

    return arr
}

unsort = [1,0,2,9,3,8,4,7,5,6]
console.log(MergeSort(unsort))

C Solution

void merge(int arr[], int low, int mid, int high){
    int i = low, j = mid + 1;    //左右指针
    int k = 0;  //工作指针
    int* temp = (int*) malloc (sizeof(int) * (high-low+1));  //暂存数组
    for(;i<=mid && j <= high; k++){  // 比较两个指针所指向的元素
        if(arr[i]<=arr[j])
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
     }


    while(i <= mid) temp[k++] = arr[i++]
    while(j <= mid) temp[k++] = arr[j++]

    for(k=0 ; k<high-low+1; k++)
        arr[low+k] = temp[k];

    return;
}

void MergeSort(int arr[], int left, int right){
    if( left < right ){
        int mid = left + (right - left) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        Merge(arr, left, mid, right);
    }
    return;
}