排序

Posted on

排序

排序是将一组对象按照某种逻辑顺序重新排列的过程。在计算机早期，大家普遍认为30%的计算周期都用在排序上。如今这个比例下降，可能原因之一是如今的排序算法更高效了，而不是说排序的重要性降低了。

既然可以使用标准库中的排序算法，大家为什么还要研究排序呢？
  • 理解算法有助于解决类似的其他问题
  • 这些算法很经典，优雅，值得去看。
  • 应用于事务处理，组合优化，天体物理学，分子动力学，语言学，基因组学，天气预报等众多领域。其中，快速排序被誉为20世纪科学和工程领域的十大算法之一。
如何来判断算法的成本
  • 计算比较和交换的数量。对于不交换元素的算法，则计算访问数组的次数。
  • 排序算法的额外开销和运行时间同等重要。
1
2
3
4
5
6
7
8
9
10

public static boolean less(Comparable v, Comparable w){
    return v.comparableTo(w) < 0;
}

public static void exch(Comparable[] a, int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}
选择排序

原理： 找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，和数组的第二个元素交换位置，直到最后一个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Selection{
    public static 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);
        }
    }
}

交换总次数：N
比较总次数：N^2 / 2
因此这个算法效率取决于比较的次数

运行时间与输入无关。

插入排序

为了给插入的元素腾出空间，我们需要将数组的其他元素在插入之前都往右移一位。当索引到达数组的最右端的时候，数组排序就完成了。
与选择排序不同的是，插入排序取决于输入元素的初始顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Insertion{

    public static void sort(Comparable[] a){
        int N = a.length;
        for(int i = 1; i < N; i++){
            //将a[i]插入到a[i-1], a[i-2],...
            for(int j = i; j > 0 && less(a[j], a[j-1]); j--){
                exch(a, a[j], a[j-1]);
            }

        }
    }

}

交换总次数：最好的情况需要0次交换，最坏的情况需要N^2 / 2次交换
比较总次数：最好的情况需要N-1次比较，最坏的情况需要N^2 / 2次比较

运行时间与输入有关。
当对一个很大且已经有序，或者接近有序的数组进行排序会比随机顺序或者逆序数组排序快的多。

希尔排序

希尔排序的思想是数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。它是基于插入排序的一种算法。
当较大的数替换到后面去，就可以减少比较的次数。

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

public class Shell{

    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while (h < N /3 ) {
            //1,4,13,40,121,...
            h = h * 3 + 1;
        }
        while(h >= 1){

            for(int i = h; h < N; i++){
                //将a[j] 插入到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;
        }
    }

}

希尔排序不需要额外的空间，而且代码量很小，当没有系统的排序函数可用时，值得优先考虑。

归并排序

即两个有序的数组归并成为一个更大的有序数组，这样的递归排序算法成为归并排序。

有序容易，难在归并，所以是如何归并的呢？

原地归并的抽象方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static void merge(Comparable[] a, int lo, int mid, int hi){
    //将数组[lo..mid]和[mid+1..hi]归并
    int i = lo, j = mid+1;
    
    for(int k = lo; k <= hi; k++){
        aux[k] = a[k]; //将a[lo..hi]复制到aux[lo..hi]中
    }

    for(int k = lo; k <= hi; k++){
        if(i > mid) a[k] = aux[j++]; //左半部分用尽了
        if(j > hi) a[k] = aux[i++]; //右半部分用尽
        if(less(aux[j], aux[i])) a[k] = aux[j++]; //右半部分小于左半部分，取右半部分
        else a[k] = aux[i++]; //取左半部分
    }

}
自顶向下的归并排序实现

基于原地归并的抽象实现了另一种递归归并，这也是分治思想的一个典型的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Merge{

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

    public 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); //归并

    }

}

这是分治思想的典型应用。比如要将a[0..15]排序，先会将其分成a[0..7]和a[8..15]排序,然后调用自己会分成a[0..3]和a[4..7]排序，a[0..3]会分成a[0..1]和a[1..2]排序，所以第一次合并就是a[0]和a[1]，a[2]和a[3]合并，在将a[0..1]和a[2..3]合并,以此类推。

假设用一颗树来表示，n表示树的层数，k 表示0到k-1层， 因此，第k层有 2^k 个数组，每个数组中有 2^(n-k)个元素，
所以每层比较的次数就是 2^k * 2^(n-k) = 2^n，n层的比较次数就是n*2^n = NlgN。

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

证明: 令C(N)表示长度为N的数组需要比较的次数，我们有C(0)=C(1)=0,对于N>1，我们有以下公式:
C(N) = C(N/2) + C(N/2) + N //左半部分比较次数，右半部分比较次数，N表示归并需要比较的次数,最少归并比较的次数为N/2

假设N为2的幂，即N=2^n,可以得到
C(2^n) = 2C(2^(n-1)) + 2^n， 同时除以 2^n 有，

C(2^n)/2^n = C(2^(n-1))/2^(n-1) + 1, 将这个公式代入 C(N/2)，有

C(2^(n-1))/2^(n-1) = C(2^(n-2))/2^(n-2) + 1，所以

C(2^n)/2^n = C(2^(n-2))/2^(n-2) + 1 + 1，所以重复n-1遍，便有

C(2^n)/2^n = C(2^0)/2^0) + n, 同时乘以 2^n, 有

C(2^n) = n*2^n = NlgN。

快速排序

快速排序是一种分治的排序算法。它将一个数组分成两个数组，两部分独立的排序。和归并排序不同的是，
归并排序是将整个排序好的小数组归并，而快速排序是当子数组排序好了的时候，整个数组自然就排好序了。

算法：

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

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); //切分：目的是找到这个j,使得左边的值都比a[j]小，右边的值都比a[j]大
        sort(a, lo, j-1); //再利用分治的思想，不断的调用自己找到最小的比较，就得到一个有序的数组
        sort(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] 放入正确的位置,即将a[lo] 与 a[j] 位置互换
        return j;
    }
}

描述下切分的策略：首先选择a[lo]作为切分的第一个元素，从左边i=lo+1开始向右扫描，当找到比a[lo]大的元素则停下来，
通过从右边j=hi开始向左扫描，当找到比a[lo]小的元素则停下来，交换这两个元素。当i>=j的时候，这一次扫描就结束了，
交换a[lo]和a[j]的元素，就可以得到a[j]左边的元素都比它小，右边的元素都比它大。

堆排序

优先队列由一个基于堆的完全二叉树表示，存储于数组pq[1..N]中，pq[0]没有使用。
完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。所有的叶子结点都在k层或者k-1层。

当我们要删除N个元素的最大元素(最小元素则相反)或者返回最大元素(最小元素则相反)时，优先队列便非常的有价值。

基于堆的优先队列算法实现:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

puclic class MaxPQ<Key extends Comparable<Key>>{

    private Key[] pq; 
    private int N = 0; //存储于pq[1..N]中,pq[0]没有使用

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

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

    public int size(){
        return N;
    }

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

    public Key delMax(){
        Key max = pq[1]; //从根结点获得最大的元素
        exch(1, N-1); //将其和最后一个结点交换
        pq[N+1] = null; //防止对象游离
        sink(1); //恢复堆的有序性
        return max;
    }

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

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

    //上浮
    private void swin(int k){
        //k/2 是k层的父亲节点
        while(k > 1 && less(k/2, k)){ 
            exch(k/2, k);
            k = k/2;
        }
    }

    //下沉
    private void sink(int k){
        while(2*k <= N){
            //k的下一节点则是k*2或k*2+1
            int j = 2*k;
            if(j < N && less(j, j+1)) j++;
            if(!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
}

堆排序算法实现：

下沉的操作是找到当前结点的所有子结点中最大的元素，交换到子结点。
因此堆排序的原理就是：找到最大元素，下沉，再交换。主要工作是在第二阶段。这里我们将最大元素删除，然后放入堆缩小后数组中空出的位置。这个过程和选择排序有点类似，但是比较的次数要少得多，因为堆提供了一种从未排序部分找到最大元素的有效办法。

1
2
3
4
5
6
7
8
9
10
11

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