归并排序（java实现）

￡神魔★判官ぃ 2022-02-05 04:57 232阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70]

**归并排序的核心思想就是把一个数组进行递归拆分成两半，然后再并。并的过程中进行排序。核心思想自行百度，其实大概过程就和上图差不多。**

# 第一步：递归拆分 #

# 第二步：递归并（并的过程中排序） #

# java实现代码如下 #

package sort;
    
    public class MergeSort { //归并排序
    	public static void sort(int arr[]) { 
    		mergesort(arr, 0, arr.length - 1);
    	}
    
    	private static void mergesort(int[] arr, int L, int R) { 
    		// TODO Auto-generated method stub
    		if(R-L<15) { //当递归到一定程度的时候，就不要再递归了，这个数组已经近乎有序，此时用插入排序。
    			//如果还用递归
    			InsertSort.sort(arr, L, R);
    			return;
    		}
    		int mid=(R+L)/2;
    		mergesort(arr, L, mid);//拆左半部分
    		mergesort(arr, mid+1, R);//拆右半部分
    		//如果左边数组中的最大值小于右边数组中的最小值，就
    		//不需要归并了，反之则归并。
    		/* * 左1 5 和 右4 7 * 1 5 4 7 这个需要归并 * 左1 2和 右3 4 * 1 2 3 4 不需要归并 */       
    		if(arr[mid]>arr[mid+1]) { 
    			merge(arr, L, mid, R);
    		}
    	}
    	private static void merge(int[] arr, int l, int mid, int r) { 
    		// TODO Auto-generated method stub
    		int[] aux=new int[r-l+1];
    		for(int i=l;i<=r;i++) { 
    			aux[i-l]=arr[i];//这里用到了角标转换 
    		}
    		int i=l,j=mid+1;
    		for(int k=l;k<=r;k++) { 
    			if(i>mid) { //左边先遍历完
    				arr[k]=aux[j-l];
    				j++;
    			}else if(j>r) { //右边先遍历完
    				arr[k]=aux[i-l];
    				i++;
    			}else if(aux[i-l]<=aux[r-l]) { //左边数组中的值小于小于右边数组的值
    				arr[k]=aux[i-l];
    				i++;
    			}else { //右边小于左边
    				arr[k]=aux[r-l];
    				j++;
    			}
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70]: /images/20220205/2f9ed47435b64cfca1d6a87d427dfa3f.png