算法入门---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)); } } }          注意此时没有对它进行优化。          自底向上的归并排序的好处：没有使用额外的数组空间。但是听说没有自顶向下的块，基本差不多。 下面贴出优化好的自顶向下的归并排序的测试时间，这是在公司电脑上的和其它测试的环境不一样仅用于此处。 100000name: 归并排序1 花费了 = 13msname: 归并排序2 花费了 = 6msname: 归并排序3 花费了 = 5msname: 归并排序4 花费了 = 7msname: 归并排序5 花费了 = 4ms平均:71000000name: 归并排序1 花费了 = 58msname: 归并排序2 花费了 = 45msname: 归并排序3 花费了 = 42msname: 归并排序4 花费了 = 41msname: 归并排序5 花费了 = 51ms平均:4710000000name: 归并排序1 花费了 = 599msname: 归并排序2 花费了 = 589msname: 归并排序3 花费了 = 581msname: 归并排序4 花费了 = 569msname: 归并排序5 花费了 = 596ms平均: 58650000000name: 归并排序1 花费了 = 3008msname: 归并排序2 花费了 = 2939msname: 归并排序3 花费了 = 2910msname: 归并排序4 花费了 = 2902msname: 归并排序5 花费了 = 2902ms平均:2932         从测试的结果分析，感觉时间复杂度不是nlogn，这个可能和数据量有关吧，再扩大数据量电脑直接报异常了，堆内存不够了。但是很明显，它能处理的数据比n^2时间复杂度的大多了，也快看很多。 时间复杂度分析：          O(nlogn) 这是该算法中最好、最坏和平均的时间性能。          这样分析理解：归并排序需要的层级是每次对2相除，分成两个子数组。那么当有n个数的时候。最终就会分logn(底数是2)个层                                   级。 而每个层级都需要进行归并操作，此时是一个  O(n)的算法复杂度。所以理解上归并的时间复杂度nlogn.注                                   意是以2为 底(2分的时候)，其实无论是不是以2为底。只是前面系数不同，而算法复杂度并不看系数，所以一                                   样。 空间复杂度为 O(n)：需要额外的空间. 稳定性： 稳定             归并排序可以设计成稳定的，也可以设计成不稳定的。既然可以设计成稳定的，那么我们一般都是设计成稳定的。拆分完毕 后,对左右两个子序列排序，你保证先排左边的，左边大于和等于右边的时候把左边的放到临时数组，这样下来就是有序的。