归并排序

归并排序Java实现

public class MergerSort {

    public static void mergerSort(int[] array) {
        int[] temp = new int[array.length];
        recSort(temp, array, 0, array.length-1);
        display(array);
    }
    // 分割数组
    private static void recSort(int[] temp, int[] array, int lower, int upper) {
        if(lower == upper) return;
        int middle = (upper + lower)/2;             // 从数组的中间位置分割
        recSort(temp, array, lower, middle);        // 递归分割左子数组
        recSort(temp, array, middle + 1, upper);    // 递归分割右子数组
        merger(temp, array, lower, middle, upper);  // 合左右子数组
    }
    // 合并两个有序数组
    private static void merger(int[] temp, int[] array, int lower, int middle, int upper) {
        int tempIndex = 0;                          // 中间数组的开始下标
        int leftIndex = lower;                      // 左边数组的开始下标
        int centerIndex = middle;                   // 左边数组的结束下标
        int rightIndex = middle + 1;                // 右边数组的开始下标
        int currTempLength = upper - lower + 1;     // 两个有序数组合并成的一个有序数组后的长度, 用于copy中间数组到原数组
        // 合并两个有序数组到中间数组
        while(leftIndex <= centerIndex && rightIndex <= upper) {
            if(array[leftIndex] < array[rightIndex]) {
                temp[tempIndex++] = array[leftIndex++];
            } else {
                temp[tempIndex++] = array[rightIndex++];
            }
        }
        // 如果右子数组没有元素了, 就把左子数组剩下的元素copy到中间数组
        while(leftIndex <= centerIndex) {
            temp[tempIndex++] = array[leftIndex++];
        }
        // 如果左子数组没有元素了, 就把右子数组剩下的元素copy到中间数组
        while( rightIndex <= upper) {
            temp[tempIndex++] = array[rightIndex++];
        }
        
        // 把排好的中间数组copy到原数组
        for(int i = 0; i < currTempLength; i++) {
            array[lower++] = temp[i];
        }
    }

    
    public static void display(int[] arr) {
        for(int x: arr) {
            System.out.print(x+" ");
        }
        
    }
    public static void main(String[] args) {
        int[] array = { 6, 3, 7, 2, 5, 1, 3, 9 };
        System.out.println("排序开始");
        long s = System.currentTimeMillis();
        mergerSort(array);
        long e = System.currentTimeMillis();
        System.out.println("\n排序结束用时"+(e-s)+"ms");
    }
}