常用排序算法总结4一一归并排序

概念

归并排序（英文：merge sort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法

原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

迭代法

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

代码实现（java）

递归版

/**
 * 归并排序，递归版
 */
public static <E extends Comparable<? super E>> List<E> mergeSort(List<E> m) {
    if (m.size() <= 1) {
        return m;
    }

    int middle = m.size() / 2;
    List<E> left = m.subList(0, middle);
    List<E> right = m.subList(middle, m.size());

    right = mergeSort(right);
    left = mergeSort(left);
    List<E> result = merge(left, right);

    return result;
}

public static <E extends Comparable<? super E>> List<E> merge(List<E> left, List<E> right) {
    List<E> result = new ArrayList<E>();
    Iterator<E> it1 = left.iterator();
    Iterator<E> it2 = right.iterator();

    E x = it1.next();
    E y = it2.next();
    while (true) {
        // change the direction of this comparison to change the direction
        // of the sort
        if (x.compareTo(y) <= 0) {
            result.add(x);
            if (it1.hasNext()) {
                x = it1.next();
            } else {
                result.add(y);
                while (it2.hasNext()) {
                    result.add(it2.next());
                }
                break;
            }
        } else {
            result.add(y);
            if (it2.hasNext()) {
                y = it2.next();
            } else {
                result.add(x);
                while (it1.hasNext()) {
                    result.add(it1.next());
                }
                break;
            }
        }
    }
    return result;
}

迭代版

/**
     * 归并排序，迭代版
     */
    public static void mergeSort(int[] nums) {
        int len = nums.length;
        int[] result = new int[len];
        int block, start;

        for (block = 1; block < len * 2; block *= 2) {
            for (start = 0; start < len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                // 两个块的起始下标及结束下标
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                // 开始对两个block进行归并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
                }
                while (start1 < end1) {
                    result[low++] = nums[start1++];
                }
                while (start2 < end2) {
                    result[low++] = nums[start2++];
                }
            }
            int[] temp = nums;
            nums = result;
            result = temp;
        }
        result = nums;
    }

算法复杂度分析

比较操作的次数介于(n*logn)/2(n log n)/2和n*logn?n+1。 赋值操作的次数是 n*logn。归并算法的空间复杂度为：O(n)。

参考文章

• 归并排序