算法4笔记/排序算法

排序类算法模板

public static void sort(Comparable[] a) {
    //排序内容
}

private static boolean less(Comparable v, Comparable w) {
    //比较两数大小，若v小于w，则返回true
    return v.compareTo(w) < 0;
}

private static void exch(Comparable[] a, int i, int j) {
    //交换两元素位置
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}

private static void show(Comparable[] a) {
    // 在单行中打印数组
    for (int i = 0; i < a.length; i++)
        StdOut.print(a[i] + " ");
    StdOut.println();
}

public static boolean isSorted(Comparable[] a) {
    //测试数组元素是否有序
    for (int i = 1; i < a.length; i++) {
        if (less(a[i], a[i - 1]))
            return false;
    }
    return true;
}

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

对于长度为 N 的数组，选择排序需要大约$N^2/ 2 $次比较和 N 次交换。

public class Selection {
    public static void sort(Comparable[] a) { // 将a[]按升序排列
        int N = a.length; // 数组长度
        for (int i = 0; i < N; i++) { // 将a[i]和a[i+1..N]中最小的元素交换
            int min = i; // 最小元素的索引
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        }
    }
    // less()、exch()、isSorted()和main()方法见“排序算法类模板”
}

冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

public class Bubble {
    public void sort(Comparable[] nums) {
        int N = nums.length;
        boolean isSorted = false;
        for (int i = N - 1; i > 0 && !isSorted; i--) {
            isSorted = true;
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) {
                    isSorted = false;
                    exch(nums, j, j + 1);
                }
            }
        }
    }
}

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要$N^2 / 4$ 次比较以及$N^2 / 4$ 次交换。最坏情况下需要$N^2 / 2$ 次比较和$N^2 / 2$ 次交换，最好情况下需要 N-1次比较和 0 次交换。

public class Insertion {
    public static void sort(Comparable[] a) { // 将a[]按升序排列
        int N = a.length;
        for (int i = 1; i < N; i++) { // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
                exch(a, j, j - 1);
        }
    }
    // less()、exch()、isSorted()和main()方法见“排序算法类模板”
}

插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

希尔排序

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

public class Shell {
    public static void sort(Comparable[] a) { // 将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... 
        while (h >= 1) { // 将数组变为h有序
            for (int i = h; i < N; i++) { // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            }
            h = h / 3;
        }
    }
    // less()、exch()、isSorted()和main()方法见“排序算法类模板”
}

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

归并排序最吸引人的性质是它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；它的主要缺点则是它所需的额外空间和 N 成正比。

• 原地归并的抽象方法

merge(a, lo, mid, hi)，它会将子数组 a[lo..mid] 和 a[mid+1..hi] 归并成一个有序的数组并将结果存放在a[lo..hi] 中。

public static void merge(Comparable[] a, int lo, int mid, int hi) { // 将a[lo..mid] 和 a[mid+1..hi] 归并
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) // 将a[lo..hi]复制到aux[lo..hi] 
        aux[k] = a[k];
    for (int k = lo; k <= hi; k++) // 归并回到a[lo..hi] 
        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++];
}

该方法先将所有元素复制到 aux[] 中，然后再归并回 a[] 中。方法在归并时（第二个 for 循环）进行了 4 个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。

• 自顶向下的归并排序

public class Merge {
    private static Comparable[] aux; // 归并所需的辅助数组

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length]; // 一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        // 将数组a[lo..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); // 归并结果（代码见“原地归并的抽象方法”）
    }
}

对于长度为 N 的任意数组，自顶向下的归并排序需要 ½NlgN 至 NlgN 次比较。

对于长度为 N 的任意数组，自顶向下的归并排序最多需要访问数组 6NlgN 次。

• 自底向上的归并排序

实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到我们将整个数组归并在一起。

public class MergeBU {
    private static Comparable[] aux; // 归并所需的辅助数组

    // merge()方法的代码请见“原地归并的抽象方法”
    public static void sort(Comparable[] a) { // 进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) // sz子数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz) // lo:子数组索引
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }
}

对于长度为 N 的任意数组，自底向上的归并排序需要 1/2NlgN 至 NlgN 次比较，最多访问数组 6NlgN 次。

• 排序算法的复杂度

1. 没有任何基于比较的算法能够保证使用少于 lg（N!）～ NlgN 次比较将长度为 N 的数组排序。
2. 归并排序是一种渐进最优的基于比较排序的算法。

快速排序

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); // 将左半部分a[lo .. j-1]排序
        sort(a, j + 1, hi); // 将右半部分a[j+1 .. hi]排序
    }
}

private static int partition(Comparable[] a, int lo, int hi) {
    // 将数组切分为a[lo..i-1], a[i], a[i+1..hi] 
    int i = lo, j = hi + 1; // 左右扫描指针
    Comparable v = a[lo]; // 切分元素
    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); // 将v = a[j]放入正确的位置
    return j; // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成 
}

将长度为 N 的无重复数组排序，快速排序平均需要 ~2NlnN 次比较（以及 1/6 的交换）。

快速排序最多需要约$N^2 / 2 $次比较，但随机打乱数组能够预防这种情况。

不存在任何基于比较的排序算法能够保证在 NH-N 次比较之内将 N 个元素排序，其中H 为由主键值出现频率定义的香农信息量。

对于大小为 N 的数组，三向切分的快速排序需要 ~(2ln2)NH 次比较。其中 H 为由主键值出现频率定义的香农信息量。

优先队列

一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。

堆排序

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。

当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

根结点是堆有序的二叉树中的最大结点。

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。

一棵大小为 N 的完全二叉树的高度为 $\lfloor lgN \rfloor$。

• 有关堆的相关操作

private boolean less(int i, int j) {
    return pq[i].compareTo(pq[j]) < 0;
}

private void exch(int i, int j) {
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

//上浮操作
private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        exch(k / 2, k);
        k = k / 2;
    }
}

//下沉操作
private void sink(int k) {
    // 当该节点的左子节点小于元素个数时循环
    while (2 * k <= N) { 
        // 将左子节点赋值给j
        int j = 2 * k; 
        // 判断左右子节点大小，如果左子节点小于右子节点，j++
        if (j < N && less(j, j + 1)) j++; 
        // 若k的左子节点大于k的右子节点，则上面if不成立，k比左子节点小就下沉，否则跳出循环
        if (!less(k, j)) break;
        
        // 若k左子节点大于右子节点且k小于左子节点，直接下沉
        // 若k左子节点小于右子节点，则第一个if成立，k和右子节点比较大小，满足条件则下沉
        exch(k, j);
        k = j;
    }
    //这里不考虑左右子节点的大小排序问题（理论上说堆有序情况下左子节点应该小于右子节点），我们要做的只是下沉k节点即可
}

对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN+1）次比较，删除最大元素的操作需要不超过 2lgN 次比较。

在一个大小为 N 的索引优先队列中，插入元素（insert）、改变优先级（change）、删除（delete）和删除最小元素（remove the minimum）操作所需的比较次数和 logN 成正比。

用下沉操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换。

• 堆排序

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int k = N / 2; k >= 1; k--)
        sink(a, k, N);
    while (N > 1) {
        exch(a, 1, N--);
        sink(a, 1, N);
    }
}

将 N 个元素排序，堆排序只需少于（2NlgN +2N）次比较（以及一半次数的交换）。

快速排序是最快的通用排序算法。