普林斯顿大学算法课 Algorithm Part I Week 3 归并排序 Mergesort

起源：冯·诺依曼最早在EDVAC上实现

基本思想：

将数组一分为（Divide array into two halves）
对每部分进行递归式地排序（Recursively sort each half）
合并两个部分（Merge two halves）

归并排序体现的是一种分治思想（Divide and conquer）

演示：　

1. 给出原数组a[]，该数组的lo到mid，mid+1到hi的子数组是各自有序的。

2. 将数组复制到辅助数组（auxiliary array）中，给两部分的首元素分别以i和j的下标，给原数组首元素以k的下标

3. 比较i下标和j下标的元素，将较小值赋到k下标位置的元素内，然后对k和赋值的下标进行递增；
该演示里j下标的元素比较小，于是将A赋到k的位置里，再对k和j递增，即j+1, k+1

4. 重复上述过程，直到比较完全部元素。

在Java中的实现

public class Merge

{

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)

        {

            assert isSorted(a, lo ,mid);        //检查a[lo..mid]是否有序

            assert isSorted(a, mid + 1, hi);      //检查a[mid+1..hi]是否有序

            for(int k = lo; k <= hi; k++)       //复制数组

                aux[k] = a[k];

            int i = lo, j = mid + 1;

            for(int k = lo; k <= hi; k++)

            {

                if      (i > mid)              a[k] = aux[j++];

                else if (j > hi)               a[k] = aux[i++];

                else if (less(aux[j], aux[i])) a[k] = aux[j++];

                else                           a[k] = aux[i++];

            }

            assert isSorted(a, lo, hi);

        }

    private static void sort(Comparable[] a, Comparable[] aux, int low, int hi)

    {

        if (hi <= lo) return;

        int mid = lo + (hi - lo) / 2;

        sort(a, aux, lo, mid);

        sort(a, aux, mid + 1, hi);

        merge(a, aux, lo, mid, hi);

    }

    public static void sort(Comparable[] a)

    {

        aux = new Comparable[a.length];

        sort(a, aux, 0, a.length - 1);

    }

}

注：Assert（断言）功能：检查表达式内的值，若为true,则程序正常运行，若为false，则抛出异常，终止运行。

性能分析：

算法复杂度为N*log(N)

优化：

问题：归并排序需要根据数组大小N开辟额外的内存

原地算法（in-place Algorithm）：占用额外空间小于等于c log(N)的排序算法。

插入排序、选择排序、希尔排序都属于原地算法。归并排序不属于原地算法。Wiki参考

Kronrod在1969年发明了原地归并排序（in-place merge），不过看起来好像不是那么有用（Challenge for the bored）

实践上的改善（practical improvements）

改善1：对小数组使用插入排序

归并排序要为小的子数组的开辟投入很多开销（开辟数组除了元素占用内存，数组本身还有固定的开销）
当子数组大小超过7，停止（Cutoff）使用插入排序

private static void sort(Comparable[] a, Comparable[] aux, int low, int hi)

{

    if （hi <= lo + CUTOFF - 1)

    {

        Insertion.sort(a, lo, hi);

        return;

        }

    int mid = lo + (hi - lo) / 2;

    sort(a, aux, lo, mid);

    sort(a, aux, mid + 1, hi);

    merge(a, aux, lo, mid, hi);

}

改善2：当数组排序好时，停止计算

两部分都已经排序完毕后，若前半部分的最后一个元素大于后半部分的第一个元素，则证明整个序列都是有序的。

private static void sort(Comparable[] a, Comparable[] aux, int low, int hi)

{

    if (hi <= lo) return;

    int mid = lo + (hi - lo) / 2;

    sort(a, aux, lo, mid);

    sort(a, aux, mid + 1, hi);

    if (!less(a[mid + 1], a[mid])) return;

    merge(a, aux, lo, mid, hi);

}

利用循环实现归并排序：Bottom-up mergesort

简单思路：循环的每一步都对上一步子数组的二倍长度做merge

巴特西

普林斯顿大学算法课 Algorithm Part I Week 3 归并排序 Mergesort

最新文章

热门文章