数据结构（十一）：归并排序

2018-03-01 11:15:55来源:https://www.jianshu.com/p/1b279dab927f作者:林塬人点击

``public static void main(String[] args) {    int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};    int[] temp = new int[arr.length];    mergeSort(arr, temp, 0, arr.length - 1);    System.out.println(Arrays.toString(temp));}public static void mergeSort(int[] a, int[] tmp, int left, int right) {    if (left < right) {        int mid = left + (right - left) / 2;        mergeSort(a, tmp, left, mid);       // 左排序        mergeSort(a, tmp, mid + 1, right);      // 右排序        merge(a, tmp, left, mid + 1, right);        // 左右合并    }}public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) {    int leftEnd = rightPos - 1;    int tmpPos = left;    int num = right - left + 1;    while (left <= leftEnd && rightPos <= right) {        if (a[left] < a[rightPos]) {            tmp[tmpPos++] = a[left++];        } else {            tmp[tmpPos++] = a[rightPos++];        }    }    while (left <= leftEnd) {        tmp[tmpPos++] = a[left++];    }    while (rightPos <= right) {        tmp[tmpPos++] = a[rightPos++];    }    for (int i = 0; i < num; i++, right--) {        a[right] = tmp[right];    }}``