首页 > 代码库 > 学习归并排序

学习归并排序

  归并排序,也是基于分治的思想,把一个数组不断切分,直到分到尾一个元素,然后两两合并,由于从一个元素开始的,所以这样每个合并的数组都是有序的, 合并只需要常数的时间完成,所以它的时间递推式为 :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 + " ");
}
}

 

学习归并排序