java算法4 合并排序

时间:2022-04-15 21:47:49
合并排序  

合并算法,指的是将两个已经排序的序列合并成一个序列的操作 

操作步骤: 
1. 建立一个数组C用来存放合并后的数 
2. 从数组A和数组B的首端开始比较,将大的元素放入C中 
3. 重复2操作,直至其中一个数组的元素被用完,则将另一个数组中剩余的元素拷贝到C中 

比较复杂度:n㏒n 
交换(赋值)复杂度:n㏒n 
优点:比较快速的排序算法 
缺点:需要额外的空间存放临时数组 

Java代码  java算法4    合并排序
  1. private static void merge(Integer[] array,final int left,final int leftEnd, final int rightEnd){  
  2.         Integer[] mergeResult = new Integer[rightEnd-left+1];  
  3.         int i = 0//mergeResult的下标  
  4.         int j = left; //left 的下标  
  5.         int k = leftEnd+1//right 的下标  
  6.           
  7.         //将两个数组中较小的元素拷贝到mergeResult中  
  8.           
  9.         while(j<=leftEnd&&k<=rightEnd){  
  10.             if(array[j]<array[k]){  
  11.                 mergeResult[i++] = array[j++];  
  12.             }else{  
  13.                 mergeResult[i++] = array[k++];  
  14.             }  
  15.         }  
  16.         //将另一个数组中剩余的元素拷贝到mergeResult中  
  17.         while(j<=leftEnd){  
  18.             mergeResult[i++] = array[j++];  
  19.         }  
  20.         while(k<=rightEnd){  
  21.             mergeResult[i++] = array[k++];  
  22.         }     
  23.         //copy mergeResult to array  
  24.         int leftPos = left;  
  25.         for(int m=0;m<mergeResult.length;m++,leftPos++){  
  26.             array[leftPos] = mergeResult[m];  
  27.         }  
  28.     }  

Java代码  java算法4    合并排序
  1. private static void mergeSort(Integer[] array,final int left,final int leftEnd, final int rightEnd){      
  2.         if(left>=rightEnd){            
  3.             return;  
  4.         }  
  5.         mergeSort(array,left,(left+leftEnd)/2,leftEnd);  
  6.         mergeSort(array,leftEnd+1,(leftEnd+1+rightEnd)/2,rightEnd);  
  7.         merge(array,left,leftEnd,rightEnd);  
  8.     }  


Java代码  java算法4    合并排序
  1. public static void mergeSort(Integer[] array){  
  2.         mergeSort(array,0,(array.length)/2,array.length-1);  
  3.     }