算法(四)排序

待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

研究排序算法的成本模型时,计算的是比较和交换的次数。

使用辅助函数 less() 和 exch() 来进行比较和交换的操作,使得代码的可读性和可移植性更好。

private boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

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

选择排序

找到数组中的最小元素,将它与数组的第一个元素交换位置。再从剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。

public class Selection {
    public void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
        }
    }
}

选择排序需要 \~N2/2 次比较和 \~N 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

插入排序

插入排序从左到右进行,每次都将当前元素插入到左部已经排序的数组中,使得插入之后左部数组依然有序。

public class Insertion {
    public void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) { for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }
}

插入排序的复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么插入排序会很快。

– 平均情况下插入排序需要 \~N2/4 比较以及 \~N2/4 次交换;
– 最坏的情况下需要 \~N2/2 比较以及 \~N2/2 次交换,最坏的情况是数组是逆序的;
– 最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了。

插入排序对于部分有序数组和小规模数组特别高效。

希尔排序

对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素,如果要把元素从一端移到另一端,就需要很多次操作。

希尔排序的出现就是为了改进插入排序的这种局限性,它通过交换不相邻的元素,使得元素更快的移到正确的位置上。

希尔排序使用插入排序对间隔 h 的序列进行排序,如果 h 很大,那么元素就能很快的移到很远的地方。通过不断减小 h,最后令 h=1,就可以使得整个数组是有序的。

public class Shell {
    public void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) { h = 3 * h + 1; // 1, 4, 13, 40, ... } while (h >= 1) {
            for (int i = h; i < N; i++) { for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}

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

归并排序

归并排序的思想是将数组分成两部分,分别进行排序,然后归并起来。

1. 归并方法

归并方法将数组中两个已经排序的部分归并成一个。

public class MergeSort {
    private Comparable[] aux;

    private void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; // 将数据复制到辅助数组
        }

        for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[i].compareTo(a[j]) < 0) a[k] = aux[i++]; // 先进行这一步,保证稳定性
            else a[k] = aux[j++];
        }
    }
}

2. 自顶向下归并排序

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

private 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);
}

因为每次都将问题对半分成两个子问题,而这种对半分的算法复杂度一般为 O(NlogN),因此该归并排序方法的时间复杂度也为 O(NlogN)。

小数组的递归操作会过于频繁,可以在数组过小时切换到插入排序来提高性能。

3. 自底向上归并排序

先归并那些微型数组,然后成对归并得到的子数组。

public void busort(Comparable[] a) {
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz += sz) {
        for (int lo = 0; lo < N - sz; lo += sz + sz) {
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
        }
    }
}

快速排序

1. 基本算法

– 归并排序将数组分为两个子数组分别排序,并将有序的子数组归并使得整个数组排序;
– 快速排序通过一个切分元素将数组分为两个子数组,左子数组小于等于切分元素,右子数组大于等于切分元素,将这两个子数组排序也就将整个数组排序了。

public class QuickSort {
    public void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private 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 void shuffle(Comparable[] array) {
        List list = Arrays.asList(array);
        Collections.shuffle(list);
        list.toArray(array);
    }
}

2. 切分

取 a[lo] 作为切分元素,然后从数组的左端向右扫描直到找到第一个大于等于它的元素,再从数组的右端向左扫描找到第一个小于等于它的元素,交换这两个元素,并不断进行这个过程,就可以保证左指针 i 的左侧元素都不大于切分元素,右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时,将切分元素 a[lo] 和 a[j] 交换位置。

private int partition(Comparable[] a, int lo, int 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);
    return j;
}

3. 性能分析

快速排序是原地排序,不需要辅助数组,但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好能将数组对半分,这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N,复杂度为 O(NlogN)。

最坏的情况下,第一次从最小的元素切分,第二次从第二小的元素切分,如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的,在进行快速排序时需要随机打乱数组。

4. 算法改进

(一)切换到插入排序

因为快速排序在小数组中也会调用自己,对于小数组,插入排序比快速排序的性能更好,因此在小数组中可以切换到插入排序。

(二)三取样

最好的情况下是每次都能取数组的中位数作为切分元素,但是计算中位数的代价很高。人们发现取 3 个元素并将大小居中的元素作为切分元素的效果最好。

(三)三向切分

对于有大量重复元素的数组,可以将数组切分为三部分,分别对应小于、等于和大于切分元素。

三向切分快速排序对于只有若干不同主键的随机数组可以在线性时间内完成排序。

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

优先队列

优先队列主要用于处理最大元素。

1. 堆

堆的某个节点的值总是大于等于子节点的值,并且堆是一颗完全二叉树。

堆可以用数组来表示,因为堆是一种完全二叉树,而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2,而它的两个子节点的位置分别为 2k 和 2k+1。这里我们不使用数组索引为 0 的位置,是为了更清晰地描述节点的位置关系。

public class MaxPQ {
    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    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;
    }
}

2. 上浮和下沉

在堆中,当一个节点比父节点大,那么需要交换这个两个节点。交换后还可能比它新的父节点大,因此需要不断地进行比较和交换操作。把这种操作称为上浮。

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) {
        int j = 2 * k;
        if (j < N && less(j, j + 1)) j++;
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

3. 插入元素

将新元素放到数组末尾,然后上浮到合适的位置。

public void insert(Key v) {
    pq[++N] = v;
    swim(N);
}

4. 删除最大元素

从数组顶端删除最大的元素,并将数组的最后一个元素放到顶端,并让这个元素下沉到合适的位置。

public Key delMax() {
    Key max = pq[1];
    exch(1, N--);
    pq[N + 1] = null;
    sink(1);
    return max;
}

5. 堆排序

由于堆可以很容易得到最大的元素并删除它,不断地进行这种操作可以得到一个递减序列。如果把最大元素和当前堆中数组的最后一个元素交换位置,并且不删除它,那么就可以得到一个从尾到头的递减序列,从正向来看就是一个递增序列。因此很容易使用堆来进行排序,并且堆排序是原地排序,不占用额外空间。

(一)构建堆

无序数组建立堆最直接的方法是从左到右遍历数组,然后进行上浮操作。一个更高效的方法是从右至左进行下沉操作,如果一个节点的两个节点都已经是堆有序,那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作,因此可以忽略叶子节点的元素,因此只需要遍历一半的元素即可。

(二)交换堆顶元素与最后一个元素

交换之后需要进行下沉操作维持堆的有序状态。

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);
    }
}

6. 分析

一个堆的高度为 logN,因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序,由于要对 N 个节点进行下沉操作,因此复杂度为 NlogN。

堆排序时一种原地排序,没有利用额外的空间。

现代操作系统很少使用堆排序,因为它无法利用缓存,也就是数组元素很少和相邻的元素进行比较。

应用

1. 排序算法的比较

快速排序是最快的通用排序算法,它的内循环的指令很少,而且它还能利用缓存,因为它总是顺序地访问数据。它的运行时间近似为 \~cNlogN,这里的 c 比其他线性对数级别的排序算法都要小。使用三向切分之后,实际应用中可能出现的某些分布的输入能够达到线性级别,而其它排序算法仍然需要线性对数时间。

2. Java 的排序算法实现

Java 系统库中的主要排序方法为 java.util.Arrays.sort(),对于原始数据类型使用三向切分的快速排序,对于引用类型使用归并排序。

3. 基于切分的快速选择算法

快速排序的 partition() 方法,会返回一个整数 j 使得 a[lo..j-1] 小于等于 a[j],且 a[j+1..hi] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 个元素。

public static Comparable select(Comparable[] a, int k) {
    int lo = 0, hi = a.length - 1;
    while (hi > lo) {
        int j = partion(a, lo, hi);
        if (j == k) return a[k];
        else if (j > k) hi = j - 1;
        else lo = j + 1;
    }
    return a[k];
}

该算法是线性级别的,因为每次正好将数组二分,那么比较的总次数为 (N+N/2+N/4+..),直到找到第 k 个元素,这个和显然小于 2N。

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 算法(四)排序

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多