排序算法之归并排序（Java实现）-蒲公英云

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

Dear 丶 2022-01-05 07:21 392阅读 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);
    }
}