排序算法之归并排序（Java实现）

Dear 丶 2022-01-05 07:21 238阅读 0赞

归并排序的思想是将局部有序的数组合并为一个大的有序数组，前提是需要保证局部数组有序，如果局部没有顺序，那么就拆分，再合并，最差的情况是，拆到两个数组都只有一个元素的时候，这时候再合并他们就成了一个有序的数组。

涉及到算法上，就是将数组直接分为两部分low~mid,(mid+1)~high，其中mid=(low+high)/2，low=0，high=length-1，然后合并，依次递归每一个拆分的小单元。

package com.xxx.algorithm.sort;
    
    public class MergeSort {
    	
    	public static void merge(int nums[],int low,int mid,int high){
    		int array[] = new int[nums.length];
    		int i = low,j=mid+1;
    		int size = 0;
    		while(i<=mid&&j<=high){
    			if(nums[i]<nums[j]){
    				array[size++] = nums[i++];
    			}else{
    				array[size++] = nums[j++];
    			}
    		}
    		while(i<=mid){
    			array[size++] = nums[i++];
    		}
    		while(j<=high){
    			array[size++] = nums[j++];
    		}
    		for(i=0;i<size;i++){
    			nums[i+low] = array[i];
    		}
    	}
    	
    	public static void print(int nums[]){
    		System.out.print("list:");
    		for(int i=0;i<nums.length;i++){
    			System.out.print(nums[i] + " ");
    		}
    		System.out.println();
    	}
    	
    	public static void sort(int nums[],int low,int high){
    		if(low<high){
    			int mid = (low+high)/2;
    			sort(nums, low, mid);
    			sort(nums, mid+1, high);
    			merge(nums, low, mid, high);
    		}
    	}
    
    	public static void main(String[] args) {
    		int[] nums = {1,4,3,2,7,6,9,5,8,0};
    		sort(nums, 0, 9);
    		print(nums);
    	}
    
    }

这个算法merge()方法中，最后需要把合并的新数组中的元素依次放入原来的数组中，这时候的语句是nums\[i+low\]=array\[i\]，而不是nums\[i\]=array\[i\]。就是这个地方需要注意。