归并排序算法
归并排序（Merging Sort）就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并最为简单和常用。
算法思想：
假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[ n/2 ]个长度为2或1的有序子序列；再两两归并，.....，如此重复，直至得到一个长度为n的有序序列为止。
算法步骤
2-路归并排序将R[ low...high ]中的记录归并排序后放入T[ low...high ]中。当序列长度等于1时，递归结束，否则：
（1）将当前序列一分为二，求出分裂点mid=(low+high)/2向下取整
（2）对子序列R[low...mid]递归，进行归并排序，结果放入S[low...mid]中；
（3）对于序列R[mid+1...high]递归，进行归并排序，结果放入S[mid+1...high]中；
（4）调用算法Merge，将有序的两个子序列S[low...mid]和S[mid+1...high]归并为一个有序的序列T[ low..high ]。
代码如下
public int[] sort(int[] nums,int low,int high){
int mid=(low+high)/2;
if(low<high){
//左边
sort(nums,low,mid);
//右边
sort(nums,mid+1,high);
//左右归并
merge(nums,low,mid,high);
}
return nums;
}
public void merge(int[] nums,int low,int mid,int high){
int[] temp=new int[high-low+1];
int j=low;
int j=mid+1
int k=0;
while(i<=mid&&j<=high){
if(nums[i]<nums[j]){
temp[k++]=nums[i++];
}else{
temp[k++]=nums[j++];
}
}
while(i<=mid){
temp[k++]=nums[i++];
}
while(j<=high){
temp[k++]=nums[j++];
}
for(int k2=0;k2<temp.length;k2++){
nums[k2+low]=temp[k2];
}
System.out.println(Arrays.toString(nums));
}
时间复杂度为O(nlog2n) 空间复杂度为O(n).
算法特点
（1）是稳定排序
（2）可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。