算法

Algs4笔记（四） --- 归并排序与快速排序

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法，归并是指将两个有序数组归并成一个更大的有序数组的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class MergeTD {
    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        sort(a, 0, N-1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo)
            return ;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo;
        int 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[i], aux[j]))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }
    // ... ...
}

以上代码实现的是自顶向下的递归归并，是计算机科学中分治思想的典型应用。研究归并操作的轨迹，可以知道sort()方法作用在于安排多次merge()方法调用的正确顺序。需要注意的一点是，我们应该一次性分配辅助空间aux[N]，如果在递归sort()中创建，将会严重影响算法效率。
既然有自顶向下的递归归并，可想而知有自底向上的迭代归并。迭代归并先归并微小数组，然后成对归并得到的子数组，如此重复，最后解决问题。与递归归并相比，迭代归并代码量更少，并且适合用链表组织的数据，因为这种方法只需要重新组织链表链接就能将链表原地排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class MergeBU {
    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];

        for (int sz = 1; sz < N; sz += sz)
            for (int i = 0; i < N-sz; i += sz+sz)
                merge(a, i, i+sz-1, Math.min(i+sz+sz-1, N-1));
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo;
        int 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[i], aux[j]))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }
    // ... ...
}

对于长度为\(N\)的任意数组，归并排序需要\(1/2NlogN\)至\(NlgN\)次比较，最多访问数组\(6NlogN\)次。归并排序是一种渐进最优的基于比较排序的算法，但并不是最完美的。归并排序需要与N成线性的辅助空间，下面的快速排序则在时间复杂度与空间复杂度都有很好的表现。

快速排序

快速排序(Quick sort)也是一种基于分治策略的排序算法，它将一个数组分成两个数组，将两部分独立地排序。这般听起来和归并排序有些相似，其实它们是互补的，归并排序将两个子数组分别排序，而后归并将整个数组排序;快速排序的策略是当两个子数组都有序时整个数组也就排好序了。归并排序中递归调用发生在处理整个数组前，快速排序递归调用则是发生在处理整个数组后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo)
            return ;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        Comparable v = a[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            while (less(a[++i], v))
                if (i == hi) break;
            while (less(v, a[--j]))
                if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    // ... ...
}

快速排序的关键在于切分方法partition(),partition()方法每次调用都可以排定一个元素，基于这点，递归调用才可以排定整个数组。快速排序是原地排序算法，上面的实现中没有使用任何辅助空间，这点就是快速排序所具有的空间复杂度优势。快速排序的内循环只是比较两个数组元素，并没有移动数据，和其它排序方法相比，这种简洁性使快速排序速度更快。将长度为\(N\)的无重复数组排序，快速排序平均需要\(～2NlnN\)次比较以及\(～1/3NlnN\)次交换，最坏的情况下，快速排序最多需要\(N^2/2\)次比较。但是随机打乱能够预防这种情况。快速排序是一个随机化的算法，排序前将整个数组打乱，就是为了保证算法性能，预防出现最坏情况下的平方级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Quick3way {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo)
            return ;
        Comparable v = a[lo];
        int i = lo + 1;
        int lt = lo;
        int gt = hi;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0)
                exch(a, i++, lt++);
            else if (cmp > 0)
                exch(a, i, gt--);
            else
                i++;
        }
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }
    // ... ...
}

以上是三向切分的快速排序的实现，对于只有若干不同主键的随机数组，归并排序的时间复杂度是线性对数的，但是三向切分快速排序则是线性的，也就是说，存在重复主键时，三向切分的快速排序性能优于归并排序。经过优化的快速排序性能优于其他基于比较的排序算法，因此快速排序应用广泛，是实现排序库函数的首选，如C中的qsort()。

参考资料