首页 > 代码库 > 学习归并排序
学习归并排序
归并排序,也是基于分治的思想,把一个数组不断切分,直到分到尾一个元素,然后两两合并,由于从一个元素开始的,所以这样每个合并的数组都是有序的, 合并只需要常数的时间完成,所以它的时间递推式为 :T(n) = 2T(n/2) + O(n), 前一项是分为两个子数组的时间复杂度,后面一项是合并两个排序好的数组的时间复杂度是O(n),
它的运行过程,在这里在网上找了一个图,很清晰的说明了这个过程:
下面是java的归并排序的demo:
public static void mergeSort(int[] a, int start, int end){
int[] sorted = new int[a.length];
if(start < end){
int mid = (start + end)/2;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end,sorted);
}
}
public static void merge(int[] a, int left, int mid, int right,int[] sorted){
int i = left;
int k = left;
int j= mid+1;
while(i <= mid && j <= right){
if(a[i] < a[j]){
sorted[k++] = a[i++];
}else{
sorted[k++] = a[j++];
}
}
//copy后半部分
while(i <= mid){
sorted[k++] = a[i++];
}
while(j <= right){
sorted[k++] = a[j++];
}
//拷贝正确的位置
for(int q = left; q <= right; q++){
a[q] = sorted[q];
}
}
public static void main(String[] args) {
int[] a = {1,4,5,32,3,44};
mergeSort(a,0,a.length-1);
for(int e : a){
System.out.print(e + " ");
}
}
学习归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。