归并排序的JavaScript实现

思想

这是一种分治算法。将原始数组切分成较小的数组，直到每个小数组只有一项，然后在将小数组归并为排好序的较大数组，直到最后得到一个排好序的最大数组。

代码

function mergeSort(arr) {

    const length = arr.length;

    if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1

        return arr;

    }

    const mid = Math.floor(length / 2);

    const left = arr.slice(0,  mid);

    const right = arr.slice(mid, length);

    return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时，才开始归并

}

function merge(left, right) {

    const result = [];

    let il = 0;

    let ir = 0;

    //left, right本身肯定都是从小到大排好序的

    while( il < left.length && ir < right.length) {

        if (left[il] < right[ir]) {

            result.push(left[il]);

            il++;

        } else {

            result.push(right[ir]);

            ir++;

        }

    }

    //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可

    while (il < left.length) {

        result.push(left[il]);

        il++;

    }

    while(ir < right.length) {

        result.push(right[ir]);

        ir++;

    }

    return result;

}

性能分析

时间复杂度：最好、平均、最坏O(nlogn)
空间复杂度: O(n), 稳定

延伸：对比C语音的归并排序

#include<stdio.h>

#include<stdlib.h>

void Merge(int *list,int *newlist,int s,int m,int t)

{

    int i,j,k;

    i=s;

    j=m+1;

    k=s;

    while(i<=m&&j<=t)

    {

        if(list[i]<=list[j])

        {

            newlist[k]=list[i];

            k++;

            i++;

        }

        else

        {

            newlist[k]=list[j];

            k++;

            j++;

        }

    }

    while(i<=m)//剩余的若是前一个序列，则其直接按并入newlist

    {

        newlist[k]=list[i];

        i++;

        k++;

    }

    while(j<=t)

    {

        newlist[k]=list[j];

        j++;

        k++;

    }

}

void MSort(int *list,int *newlist,int s,int t)

{

    int *newlist2;

    int m;

    newlist2=(int *)malloc((t-s+1)*sizeof(int));//分配一个新数组，和list等长

    if(s==t)

    {

        newlist[s]=list[s];

    }

    else

    {

        m=(s+t)/2;

        MSort(list,newlist2,s,m);//将list[s]……list[m]递归归并为有序的newlist2[s]……newlist2[m]

        MSort(list,newlist2,m+1,t);//将list[m+1]……list[t]递归归并为有序的newlist2[m+1]……newlist2[t]

        Merge(newlist2,newlist,s,m,t);//将newlist2[s]……newlist2[m]和newlist2[m+1]……newlist2[t]归并到newlist[s]……newlist[t]

    }

}

void MergeSort(int *list,int *newlist,int n)

{

    MSort(list,newlist,0,n-1);

}

main()

{

    int list[10],n=10,i,newlist[10];

    printf("请输入10个整数：\n");

    for(i=0;i<10;i++)

    {

        scanf("%d",&list[i]);

    }

    MergeSort(list,newlist,10);

    for(i=0;i<10;i++)

    {

        printf("%d",newlist[i]);

    }

    system("pause");

}

巴特西

归并排序的JavaScript实现

思想

代码

性能分析

延伸：对比C语音的归并排序

最新文章

热门文章