排序算法篇（归并排序）
归并排序
归并排序是另一类不同的排序方法，所谓归并,就是把两个或者两个以上的有序表合并成一个新的有序表的过程。
归并排序的基本思想:
将一个含有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).
稳定性:
归并排序不涉及到交换,因此它是一种稳定的排序算法。
归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越，但需要与序列等长的辅助空间。