数据结构-归并排序

java实现归并排序算法

源代码

public class MergeSort extends DataCrol {
    // 合并两个已排好序的数组A[left...mid]和A[mid+1...right]
    void merge(int A[], int left, int mid, int right) {
        int len = right - left + 1;
        int[] temp = new int[len];// 辅助空间O(n)
        int index = 0;
        int i = left;                   // 前一数组的起始元素
        int j = mid + 1;                // 后一数组的起始元素
        while (i <= mid && j <= right) {
            temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 带等号保证归并排序的稳定性
        }
        while (i <= mid) {
            temp[index++] = A[i++];
        }
        while (j <= right) {
            temp[index++] = A[j++];
        }
        for (int k = 0; k < len; k++) {
            A[left++] = temp[k];
        }
    }

    // 递归实现的归并排序(自顶向下)
    void mergeSortRecursion(int A[], int left, int right) {
        if (left == right)    // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
            return;
        int mid = (left + right) / 2;
        mergeSortRecursion(A, left, mid);
        mergeSortRecursion(A, mid + 1, right);
        merge(A, left, mid, right);
    }

    // 非递归(迭代)实现的归并排序(自底向上)
    void mergeSortIteration(int A[]) {
        int len = A.length;
        int left, mid, right;// 子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right]
        for (int i = 1; i < len; i *= 2) {       // 子数组的大小i初始为1，每轮翻倍
            left = 0;
            while (left + i < len) {              // 后一个子数组存在(需要归并)
                mid = left + i - 1;
                right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够
                merge(A, left, mid, right);
                left = right + 1;               // 前一个子数组索引向后移动
            }
        }
    }

    @Override
    public void sort(int[] array) {
//        mergeSortIteration(array);
        mergeSortRecursion(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = DataCrol.createRandomArray(20);
        DataCrol.print(array);
        mergeSort.sort(array);
        DataCrol.print(array);
        mergeSort.timeTest(10000000);
    }
}