算法入门---java语言实现的归并排序小结

 
 /**            
      
 * 归并排序 基本思想:将一个无序的集合，一半一半的递归的分成好几个有序的子集合(最终分成只有一个元素，那么也就相当于是有序了),            
      
 * 然后在两两的依次归并到一块。                重要的核心在于这个归并的过程。 归并的简单思想：       
      
 * 首先这两个子序列是有序的，那么给定两个变量分别指向两个子序列的第一个元素。依次的比较谁小放在前面，此处需要借助一下一个            
      
 * 临时的数组，                最后排完的时候谁没排完直接全部放在最后即可。       
      
 * 归并排序一个关键点就是你应该定义好索引，按照你的索引来写好代码。比如            
      
 *     临时数组{ ,C, , , , , , } 索引指向 将要添加进去的位置。如当前C前面都要数，那么就指向C            
      
 *     需要归并的子数组{A, , , , , } 、 B, , , , , } 索引指向当前需要比较的数值所在。            
      
 *     A 、 B需要比较然后往临时数组存入，那么就指向A B            
      
 *                 
      
 *             
      
 * @author zhaoyuan            
      
 *             
      
 */            
      
 public class MergeSort {            
      
  
      
  
      
 /**            
      
 * 注意参数代表            
      
 * @param src 源数组            
      
 * @param left 数组的要排序的左边最小的索引            
      
 * @param right 数组要排序的右边最后一个索引 (所以你传值的时候就不能传数组长度)            
      
 */            
      
 public static void sort(int[] src,int left,int right){            
      
  
      
 if(left >= right){//大于等于都不需要再拆分了。            
      
 return;            
      
 }            
      
 //这边可能溢出,这个mid是左子序列的最后一个元素的索引            
      
 //比如: 1 2 3 4   mid = (0+3)/2 = 1  也就是元素2.            
      
 //比如：1 2 3 4 5 mid = (0+4)/2 = 2 也就是 元素3,此时按照 (1 2 3) (4 5)划分.            
      
 int mid = (left + right)/2;            
      
 //此处是先拆分在合并的顺序            
      
 //拆分左子序列。            
      
 sort(src,left,mid);            
      
 sort(src,mid+1,right);            
      
 //拆分完毕后就行合并。            
      
 merge(src,left,mid,right);            
      
 }            
      
  
      
 /**            
      
 *  合并：src[left... mid] src[mid+1.....right],注意这两个已是有序的集合            
      
 *  一定要注意参数的代表，此时的设计是按照闭区间来的。            
      
 * @param src 数据源            
      
 * @param left 要排序的序列的左边的最小索引            
      
 * @param mid  要排序的序列的左边的最大索引            
      
 * @param right 要排序的序列的右边的最大索引(右边的最小索引就是 mid+1嘛)            
      
 */            
      
 public static void merge(int[] src,int left,int mid,int right){            
      
 //归并排序单纯的依靠在当前数组移动、赋值等来实现最终排序比较难。            
      
 //我们此处是利用一个额外的数组的方式来实现的。核心思想还是比较然后放入数组合适的位置。            
      
 int[] temp = new int[right-left+1];//因为我们传入的都是索引，所以长度应该最后+1.            
      
  
      
 //此处有个小思想，此处你需要控制三个索引，那么一般来说你都要把这些索引先存一下。            
      
 int i = left;//左边需要比较的元素的索引            
      
 int j = mid+1;//右边需要比较的元素的索引            
      
 int k = 0;//将要放入的临时数组的索引。            
      
  
      
 //两个处在有交集的时候。此时我们传入的都是索引，所以i<= mid都可以(mid是最后一个索引)。            
      
 //right也同理,它是最后一个索引            
      
 while((i<=mid)&&(j<=right)){//也可以看出你把参数中的索引先保存一份的必要性。            
      
 //然后比较找到比较小的放在前面，并且相应的变量++,等于可以保证稳定.            
      
 if(src[i] <= src[j]){            
      
 //证明应该把src[i]放入到临时数组temp当中            
      
 //temp[k] = src[i];            
      
 //赋值完毕后应该，k应该向后移动一位等待下一个输入.            
      
 //k++;            
      
 //i也该向后移动一位，去找下一个需要比较的元素。            
      
 //i++;            
      
 //优化代码结构：            
      
 temp[k++] = src[i++];            
      
 }else{            
      
 //道理同上            
      
 temp[k++] = src[j++];            
      
 }            
      
 //以上都不会超出索引？            
      
 //分析： i、j是有可能超出mid或者right的。但是超出以后我们并没有对相关的数组元素            
      
 //    进行赋值或者什么的，并不会处问题。            
      
 //    k ：是不会超出它的范围的，因为i和j的最大值加起来再加1才是它的最大值。            
      
 }            
      
 //接下来再分析某一个数组比另一个长的时候,此时应该把长的那个多余的元素全放入temp中,在前面的while玄幻外面            
      
 //当左序列还未排完            
      
 while(i <= mid){//此时必然是右边排完了就是j>right了，但是i还<=mid,注意把等于考虑进去。            
      
 temp[k++] = src[i++];            
      
 }            
      
 //当右边序列还未排完            
      
 while(j <= right){//同理            
      
 temp[k++] = src[j++];            
      
 }            
      
 //排完以后把临时数组赋值到对应的原数组的位置。            
      
 for(int t = 0;t <temp.length;t++){            
      
 src[left++] = temp[t];            
      
 }            
      
 }            
      
  
      
  
      
 }            
     
    

简单的优化：

 
 public static void sort(int[] src,int left,int right){            
      
  
      
 //if(left >= right){            
      
 //    return;            
      
 //}            
      
 //优化1:在元素比较少时用插入排序. 亲测这个优化效率提高还是很明显的！            
      
 //     原因：首先是数组比较小的时候近乎有序的概率很高,而且从2个相合并开始每次合并的时候最序列都是有序的            
      
 //          其次无论是n^2、nlogn 算法复杂度，其实前面都有系数的。而在n比较小的时候系数就很关键了。插入            
      
 //          的系数比归并小。            
      
 if(right- left<= 15 ){            
      
 InsertSort.sort(src, left, right);            
      
 return;            
      
 }            
      
 int mid = (left + right)/2;            
      
 sort(src,left,mid);            
      
 sort(src,mid+1,right);            
      
 //优化2:因为左右子序列本来就是有序的，所以当左边的序列小于右边的序列的时候本身            
      
 //     就是有序的，不需要再合并。感觉上没有花多少，毕竟在较为有序的情况下里面也没执行多少。            
      
 //     当然有些时候还会产生影响(毕竟这个也需要占时间.)            
      
 if(src[mid] > src[mid+1]){            
      
 //拆分完毕后就行合并。            
      
 merge(src,left,mid,right);            
      
 }            
      
 }            
     
    

插入排序：

 
 public static void sort(int[] src, int left, int right) {            
      
 //一定要注意这时候传入的是区间，所以i = left+1, i <=right;            
      
 //不要从i = 0开始到，len这样！            
      
 for (int i = left+1; i <= right; i++) {            
      
 int temp = src[i];            
      
 int j;            
      
 for (j = i; j > 0 && temp < src[j - 1]; j--) {            
      
 src[j] = src[j - 1];            
      
 }            
      
 src[j] = temp;            
      
 }            
      
 }            
     
    

自底向上的归并排序(网图)：

 
 /**            
      
 * 自底向上的的归并。            
      
 * 就是以当前数组为考虑的基点，不再进行拆分，而是直接进行归并，            
      
 * 先是把一个个元素归并成两两有序的，再把两两有序的归并成四四有序的依次类推，直到归并            
      
 * 后大于数组的长度那么就排序完成了。            
      
 *             
      
 */            
      
 public static void sort(int[] src){            
      
 int len = src.length;            
      
 //此处循环遍历的是归并的每个子数组的元素的个数，一开始子数组是1，然后子数组变成2，            
      
 //然后变成4，然后变成8这样一次类推，直到它变成的元素小于数组的长度.            
      
 //      1 2 3 4 5             
      
 //第二次 ....(1 2)、 (3 4)、 5; 1*2            
      
 //第三次....(1 2 3 4)、5; 1*2*2            
      
 //第四次....(1 2 3 4 5); 1*2*2            
      
 for(int i = 1;i < len;i=2*i){            
      
 //内层循环是用来实现两个子元素的归并的,注意每次是跳2*i个索引            
      
 //因为归并完比后，他们应该移动2倍的i的距离。            
      
 //for(int j=0;j<len;j=j+2*i){            
      
 //合并src[j...j+i-1]、src[j+i...j+i+i-1]            
      
 //你就一个一个序列的想，就像第一个元素肯定是从j开始然后他有i个元素，但是我们此时要传入索引            
      
 //所以就是j-----j+i-1,对于要合并右边的子序列此时就是j+i------j+i+i+i-1.(不是最终长度哦)            
      
 //    merge(src,j,j+i-1,j+i+i-1);            
      
 //}            
      
 //但是如上写的时候可能会出问题，因为我们没有考虑边界的问题。            
      
 //如：当分完后右边的那个子序列不够数的时候我们再src[j+i+i-1]必然就越界了。            
      
 //   还有当右边压根没有序列的时候也不需要排列啊，你也会出错。            
      
 //进行优化            
      
 //改成符合j+i小于len时才合并，否则就不合并。因为j+i>=i证明就没有序列或者只有一个序列，此时它就是有序的合并什么？            
      
 for(int j=0;j+i < len;j = j+2*i){            
      
 //防止最后超出数组范围。取两个的最小值。(每次都这么算感觉增加了开销啊)            
      
 merge(src,j,j+i-1,Math.min(j+i+i-1,len-1));            
      
 }            
      
 }            
      
 }            
     
    

         注意此时没有对它进行优化。          自底向上的归并排序的好处：没有使用额外的数组空间。但是听说没有自顶向下的块，基本差不多。

下面贴出优化好的自顶向下的归并排序的测试时间，这是在公司电脑上的和其它测试的环境不一样仅用于此处。

 
 100000            
      
 name: 归并排序1 花费了 = 13ms            
      
 name: 归并排序2 花费了 = 6ms            
      
 name: 归并排序3 花费了 = 5ms            
      
 name: 归并排序4 花费了 = 7ms            
      
 name: 归并排序5 花费了 = 4ms            
      
  
      
 平均:7            
      
  
      
 1000000            
      
 name: 归并排序1 花费了 = 58ms            
      
 name: 归并排序2 花费了 = 45ms            
      
 name: 归并排序3 花费了 = 42ms            
      
 name: 归并排序4 花费了 = 41ms            
      
 name: 归并排序5 花费了 = 51ms            
      
  
      
 平均:47            
      
  
      
 10000000            
      
  
      
 name: 归并排序1 花费了 = 599ms            
      
 name: 归并排序2 花费了 = 589ms            
      
 name: 归并排序3 花费了 = 581ms            
      
 name: 归并排序4 花费了 = 569ms            
      
 name: 归并排序5 花费了 = 596ms            
      
  
      
 平均: 586            
      
  
      
 50000000            
      
 name: 归并排序1 花费了 = 3008ms            
      
 name: 归并排序2 花费了 = 2939ms            
      
 name: 归并排序3 花费了 = 2910ms            
      
 name: 归并排序4 花费了 = 2902ms            
      
 name: 归并排序5 花费了 = 2902ms            
      
  
      
 平均:2932            
     
    

        从测试的结果分析，感觉时间复杂度不是nlogn，这个可能和数据量有关吧，再扩大数据量电脑直接报异常了，堆内存不够了。但是很明显，它能处理的数据比n^2时间复杂度的大多了，也快看很多。

时间复杂度分析：          O(nlogn) 这是该算法中最好、最坏和平均的时间性能。

         这样分析理解：归并排序需要的层级是每次对2相除，分成两个子数组。那么当有n个数的时候。最终就会分logn(底数是2)个层                                   级。 而每个层级都需要进行归并操作，此时是一个  O(n)的算法复杂度。所以理解上归并的时间复杂度nlogn.注                                   意是以2为 底(2分的时候)，其实无论是不是以2为底。只是前面系数不同，而算法复杂度并不看系数，所以一                                   样。 空间复杂度为 O(n)：需要额外的空间. 稳定性： 稳定             归并排序可以设计成稳定的，也可以设计成不稳定的。既然可以设计成稳定的，那么我们一般都是设计成稳定的。拆分完毕 后,对左右两个子序列排序，你保证先排左边的，左边大于和等于右边的时候把左边的放到临时数组，这样下来就是有序的。