排序算法篇（归并排序）

归并排序

归并排序是另一类不同的排序方法，所谓归并,就是把两个或者两个以上的有序表合并成一个新的有序表的过程。

归并排序的基本思想:

将一个含有n个序列的有序表看成是n个长度为1的有序表,然后两两归并,得到[n/2]个长度为2的有序表,然后再两两归并,直到得到一个长度为n的有序表为止。

下面是归并排序的一个简单的例子:

初始值【49】【38】【65】【97】【76】【13】【27】

看成由长度为1的7个子序列组成

第一次合并之后【3849】【6597】【1376】【27】

看成由长度为1或2的4个子序列组成

第二次合并之后【38496597】【132776】

看成由长度为4或3的2个子序列组成

第三次合并之后【13273849657697】

归并排序的JAVA实现:

publicclassMergeSort{

/**

*归并排序先将初始的序列表看成是n个长度为1的有序表(1)定义指针i,指向第一个序列表的第一个元素

*(2)定义指针j，指向第二个序列表的第一个元素(3)比较i,j指向的元素大小，若前者大，将后者插入到新表中否则，把前者插入到后表中

*(4)直到取完第一个序列表或者第二个序列表为止

*

*@paramargs

*/

publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

int[]num={51,38,49,27,62,05,16};

int[]num1=newint[7];

num=mergesort(num,0,num.length-1,num1);

for(inti:num){

System.out.print(i+"");

}

}

privatestaticint[]mergesort(int[]num,ints,intt,int[]num1){

intm;

int[]num2=newint[t+1];

if(s==t)

num1[s]=num[s];

else{

m=(s+t)/2;

mergesort(num,s,m,num2);//左半部分递归调用

mergesort(num,m+1,t,num2);//右半部分递归调用

merg(num2,s,m,t,num1);//由num2去归并，返回的值放到num1中,num1赋新值，其实就是更新num2,然后让num2再去归并，返回新的num1

}

returnnum1;

}

//有序表的合并

privatestaticvoidmerg(int[]num,intl,intm,intn,int[]num1){

System.out.print("l="+l+"m="+m+"n="+n);

System.out.println();

inti,j,k;

i=l;

j=m+1;

k=l;

while(i<=m&&j<=n){

if(num[i]<num[j])

num1[k++]=num[i++];

else{

num1[k++]=num[j++];

}

}

while(i<=m){

num1[k++]=num[i++];

}

while(j<=n){

num1[k++]=num[j++];

}

}

}

性能分析:

时间复杂度:

由于归并的趟数,等于树的高度Logn,每趟归并需要移动记录n次,因此归并排序的时间复杂度为nlogn.

空间复杂度:

从上面的算法可以看出,需要一个辅助空间num2,其长度等于n，所以归并排序的辅助空间为O(n).

稳定性:

归并排序不涉及到交换,因此它是一种稳定的排序算法。

归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越，但需要与序列等长的辅助空间。