思想
这是一种分治算法。将原始数组切分成较小的数组，直到每个小数组只有一项，然后在将小数组归并为排好序的较大数组，直到最后得到一个排好序的最大数组。
代码
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");
}