java数组合并排序(归并排序java实现)

1. 归并排序的介绍2. 归并排序代码实现：3. 运行时间测量4. 复杂度分析

下面是归并排序学习笔记，包括算法过程展示，代码分析，复杂度分析

归并排序采用了分治递归的思想
首先进行的时分治，将一个数组或者容器两两拆分成子数组，直到子数组的大小为1 。
接下来就是递归合并，对分支的子数组两两排序合并。

1.分治：

在分治的时候，我们将规模为： n n n 的问题分为 2 个规模为 n 2 frac{n}{2} 2n​ 的问题，求解两个子问题（也就是对两个子数组进行排序）需要时间为 2 T ( n 2 ) 2T(frac{n}{2}) 2T(2n​)，设分解问题需要时间： D ( n ) D(n) D(n)

2.递归合并：

设合并子问题需要时间： C ( n ) C(n) C(n)，这样就有递归式： T ( n ) = 2 T ( n 2 ) + D ( n ) + C ( n ) T(n)=2T(frac{n}{2})+D(n)+C(n) T(n)=2T(2n​)+D(n)+C(n)

归并排序动图展示：

首先对以上过程模型化：

先是分治：定义分治的函数为： m e r g e ( A , l , r ) merge(A,l,r) merge(A,l,r)
         qquad~~~~~~~~         那么我们就先找到数组的中点： m i d = ⌊ l + r 2 ⌋ mid=lfloor frac{l+r}{2} rfloor mid=⌊2l+r​⌋
         qquad~~~~~~~~         然后在对 A [ l … m i d ]   和   A [ m i d + 1 … r ] A[ldots mid]~和~A[mid+1dots r] A[l…mid] 和 A[mid+1…r] 进行 m e r g e S o r t mergeSort mergeSort 函数
         qquad~~~~~~~~         直到： l = = r l==r l==r然后归并：我们要对数组： A 1 [ l … m i d ]   与   A 2 [ m i d + 1 … r ] A_1[ldots mid]~与~A_2[mid+1dots r] A1​[l…mid] 与 A2​[mid+1…r] 进行合并排序。
         qquad~~~~~~~~         排序的思路就是取两个哨兵 i , j i,j i,j分别在两个数组的头部，再定义一个新的数组： n e w A r r a y [ l … r ] newArray[ldots r] newArray[l…r]
         qquad~~~~~~~~         然后依次遍历两个数组： i f A 1 [ i ] < A 2 [ j ] n e w A r r a y [ i ] = A 1 [ i + + ] i f A 2 [ j ] > A 1 [ i ] n e w A r r a y [ j ] = A 2 [ j + + ] begin{array}{lll}if&A_1[i]A_1[i]&newArray[j]=A_2[j++]end{array} ifif​A1​[i]A1​[i]​newArray[i]=A1​[i++]newArray[j]=A2​[j++]​
         qquad~~~~~~~~         直到遍历结束

代码展示：

这里我们使用Java的内置方法：System.nanoTime 来对代码进行计时，在后面的文章中，我们会使用不同的方法来计算运行时间，有兴趣的可以继续关注哦。注意：System.nanoTime的单位是纳秒

package com.company;
import java.io.IOException;
import  java.util.*;
import java.util.Arrays;

public class Main{
    public static int[] nums;
    public static int size;
    public static int[] result;

    public static void mergeSort(int l, int r){
        if(l == r)
            return ;
        //先进行分治
        int mid = (l + r) / 2;
        mergeSort(l, mid);
        mergeSort(mid+1, r);

        //下面进行归并排序
        int n1 = l, n2 = mid+1, k = l;
        while(n1 <= mid && n2 <= r){
            if(nums[n1] < nums[n2]) {
                result[k] = nums[n1];
                k++;n1++;
            }
            else {
                result[k] = nums[n2];
                k++;n2++;
            }
        }
        while(n1 <= mid) {
            result[k] = nums[n1];
            k++;n1++;
        }
        while(n2 <= r) {
            result[k] = nums[n2];
            k++;n2++;
        }
        for(int i = l; i <= r; i++){
            nums[i] = result[i];
        }
    }
    //生成随机数组
    public static void createArray(){
        Random rand = new Random();
        for(int i = 0; i < size; i++)
            nums[i] = rand.nextInt(1000);
    }
    //打印待排序数组
    public static void printNums(){
        int step = 20;
        for(int i = 0; i < size; i++){
            if(i == step){
                step += 20;
                System.out.println();
            }
            System.out.print(nums[i] + " ");
        }
    }
    //打印排序的结果数组
    public static void printResult(){
        int step = 20;
        for(int i = 0; i < size; i++){
            if(i == step){
                step += 20;
                System.out.println();
            }
            System.out.print(result[i] + " ");
        }
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        System.out.print("输入数组的大小："); size = in.nextInt();
        nums = new int[size];
        result = new int[size];
        System.out.println("输入排序前的数组");
        createArray();
        printNums();

        System.out.println("n" + "输入排序后的数组");
        double start_time = System.nanoTime();
        mergeSort(0,size-1);
        double end_time = System.nanoTime();
        double time = end_time - start_time;
        time /= 1000000;
        printResult();
        System.out.println("n" + "运行时间为：" + time + "毫秒");

        in.close();
    }
}

输入展示：

下面我们将 s i z e size size 作为数组输入： s i z e = [ 1000 5000 10000 50000 100000 500000 1000000 5000000 10000000 ] size=begin{bmatrix}1000&5000&10000&50000&100000&500000&1000000&5000000&10000000end{bmatrix} size=[1000​5000​10000​50000​100000​500000​1000000​5000000​10000000​]
得到结果：

观察： m e r g e S o r t mergeSort mergeSort 函数：
m e r g e S o r t ( A , l , r ) mergeSort(A,l,r) mergeSort(A,l,r)
i f    l < r qquad if~~l m i d = ⌊ l + r 2 ⌋ qquad qquad mid= lfloor frac{l+r}{2} rfloor mid=⌊2l+r​⌋
m e r g e S o r t ( A , l , m i d ) qquad qquad mergeSort(A,l,mid) mergeSort(A,l,mid)
m e r g e S o r t ( A , m i d + 1 , r ) qquad qquad mergeSort(A,mid+1,r) mergeSort(A,mid+1,r)
m e r g e ( A , l , r ) qquad qquad merge(A,l,r) merge(A,l,r)
其中函数中的： m e r g e ( A , l , r ) merge(A,l,r) merge(A,l,r) 函数的复杂度为： Θ ( n ) Theta(n) Θ(n)
那么， m e r g e S o r t ( ) mergeSort() mergeSort() 函数的时间为： T ( n ) = 2 T ( n 2 ) + Θ ( n ) T(n)=2T(frac{n}{2})+Theta(n) T(n)=2T(2n​)+Θ(n)
由主定理得到， T ( n ) = Θ ( n lg ⁡ n ) T(n)=Theta(nlg n) T(n)=Θ(nlgn)