Dotcpp  >  编程教程  >  Java数组  >  Java归并排序(Merge Sort)

Java归并排序(Merge Sort)

点击打开在线编译器,边学边练

归并排序(Merge Sort)是建立在归并操作上的一种有效的稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。


归并排序将两个有序的子序列合并得到一个完全有序的序列,即先使每个子序列有序,再使子序列段间有序。若将两个有序的列表合并成一个有序的列表,我们称之为二路归并


归并排序的速度仅次于快速排序,时间复杂度为O(nlogn)。其拆分过程中使用了二分思想,是一个递归的过程,为了减少在递归过程中不断开辟空间的问题,我们可以在归并排序之前,先开辟出一个临时空间,在递归过程中统一使用此空间进行归并即可。


例如:

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{86,23,7,45,19,10};
        int left = 0;
        int right = arr.length-1;
        int[] tem = Arrays.copyOf(arr,arr.length);
        print(arr);
        mergeSort(arr,left,right,tem);
        print(arr);
    }
    public static void mergeSort(int[] arr,int left,int right,int[] tem) {
        if(right-left<1) {
            return;
        }
        int mid = left + (right-left)/2;
        mergeSort(arr,left,mid,tem);
        mergeSort(arr,mid+1,right,tem);
        merge(arr,left,mid,right,tem);
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] tem) {
        int index = 0;
        int l = left,r = mid+1;
        while(l <= mid && r <= right) {
            if(arr[l]<arr[r]) {
                tem[index++] = arr[l++];
            }else{
                tem[index++] = arr[r++];
            }
        }
        while(l <= mid) {
            tem[index++] = arr[l++];
        }
        while(r <= right) {
            tem[index++] = arr[r++];
        }
        for(int i=0;i<(right-left+1);i++) {
            arr[left+i] = tem[i];
        }
    }
    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }
}


运行结果如下:

86  23  7   45  19  10 
7   10  19  23  45  86



本文固定URL:https://www.dotcpp.com/course/896

Java教程
第一章 Java入门
第二章 Java运算符和表达式
第三章 Java流程控制
第四章 Java类和对象
第五章 Java子类与继承
第六章 Java接口与实现
第七章 Java内部类与异常类
第八章 Java常用实用类
第九章 Java输入输出流
第十章 Java数组
Dotcpp在线编译      (登录可减少运行等待时间)