本文共 1432 字，大约阅读时间需要 4 分钟。

import java.util.Arrays;import java.util.Random;public class MergeSort {    public static void main(String args[]) {        int[] array = fillArray();        split(array, 0, array.length - 1);        System.out.println(Arrays.toString(array));    }    private static int[] fillArray() {        Random random = new Random();        int[] array = new int[100];        for (int i = 0; i < 100; i++) {            array[i] = random.nextInt(1000);        }        return array;    }    public static void split(int[] array, int left, int right) {        if (left >= right) {            return;        }        int mid = (left + right) / 2;        split(array, left, mid);        split(array, mid + 1, right);        merge(array, left, mid, right);    }    private static void merge(int[] array, int left, int mid, int right) {        int len = right - left + 1;        int[] tmp = new int[len];        int i = left;        int j = mid + 1;        int k = 0;        while (i <= mid && j <= right) {            if (array[i] <= array[j]) {                tmp[k++] = array[i++];            } else {                tmp[k++] = array[j++];            }        }        while (i <= mid) {            tmp[k++] = array[i++];        }        while (j <= right) {            tmp[k++] = array[j++];        }        int p = left;        int q = 0;        while (q < k) {            array[p++] = tmp[q++];        }    }}

• 时间复杂度：O(nlog(n))
• 空间复杂度：O(log(n))

转载地址：http://bnaii.baihongyu.com/