归并排序
介绍
归并算法采取了分治的策略，类似完全二叉树，分是指将数组通过递归拆分成子序列，治是指将两个有序的子序列合并为一个有序序列。
代码
public class merge_sort{
public static void sort(int[] array
){
int[] temp
= new int[array
.length
];
sort(arr
,0,array
.length
-1,temp
);
}
private void sort(int[] array
, int left
, int right
, int[] temp
){
if(left
< right
){
int mid
= (left
+ right
) / 2;
sort(array
, left
, mid
, temp
);
sort(array
, mid
+1, right
, temp
);
merge(array
,left
,mid
,right
,temp
);
}
}
private void merge(int[] array
, int left
, int mid
, int right
, int[] temp
){
int i
= left
;
int j
= mid
+ 1;
int index
= 0;
while(i
<= mid
&& j
<= right
){
if(array
[i
] <= array
[j
])
temp
[index
++] = array
[i
++];
else
temp
[index
++] = array
[j
++];
}
while(i
<= mid
)
temp
[index
++] = array
[i
++];
while(j
<= right
)
temp
[index
++] = array
[j
++];
int index
= 0;
while(left
< right
)
array
[left
++] = temp
[index
++];
}
}
性能分析
时间复杂度
归并排序每一次治阶段的时间复杂度为O(n)，分的次数为完全二叉树的深度O(log2n)，所以归并排序的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)
空间复杂度
归并排序的需要申请一个新数组进行归并，空间复杂度为O(n)
稳定性
在利用双指针归并时，可以实现相同数字不交换，故为稳定排序
