这篇文章主要介绍“java怎么实现归并排序”,在日常操作中,相信很多人在java怎么实现归并排序问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java怎么实现归并排序”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
public class MergeSort {
public static int arr[] = {2,4,7,8,9,4,5,1,2,3,6,8,7,8,54,4,2,58,47,5,8,4,2,5,0,0};
public static void main(String[] args) {
sort(0,arr.length-1); //排序
print(); //打印
}
//拆分
public static void sort(int left,int right){
if(left >= right)
return;
//递归终止条件,一个子数组只有一个或两个元素
if(right-left==1){
if(arr[left]>arr[right]){
int t = arr[left];
arr[left] = arr[right];
arr[right] = t;
}
return;
}
//递归分解
int mid = (left + right)/2;
sort(left,mid);
sort(mid+1,right);
//合并
merge(left,mid,right);
}
//合并
public static void merge(int left,int mid,int right){
int i = left;
int j = mid+1;
int k = 0;
//开辟临时数组,合并两个有序子数组
int temp[] = new int[right-left+1];
while(i<=mid && j<=right){
if(arr[i]<arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while(i<=mid){
temp[k++] = arr[i++];
}
while(j<=right){
temp[k++] = arr[j++];
}
//将临时数组合并到原来数组中
k = 0;
for(i = left;i<=right;i++){
arr[i] = temp[k++];
}
}
/**
* 打印
*/
public static void print(){
for(int a:arr){
System.out.print(a+",");
}
System.out.println();
}
}
归并排序,平均复杂度nlogn
到此,关于“java怎么实现归并排序”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。