Jialong's Blog

Do things I love, and seek happiness.

0%

《算法(第4版)》学习笔记——(一)排序

初级排序算法

选择排序

算法描述

首先找到数组中最小的一个元素,将其与数组的第一个元素进行交换;再在剩余的元素找到最小的一个元素,将其与数组的第二个元素进行交换。如此循环往复,直到将整个数字排序。

代码实现

1
public class Selection {
2
    public static void sort(Comparable[] a)
3
    {
4
        //将a按照升序排列
5
        int N = a.length;
6
        for (int i = 0; i < N; i++)
7
        {
8
            int min = i;
9
            for (int j = i + 1; j < N; j++)
10
            {
11
                if (less(a[j], a[min]))
12
                    min = j;
13
            }
14
            exch(a, i ,min);
15
        }
16
    }
17
}

性能分析

  • 对长度为$N$的数组,选择排序大概需要$N^2/2$次比较和$N$次交换。
  • 该算法运行时间与输入无关,数据的移动是最少的。

插入排序

算法描述

插入排序当前索引左边的所有元素都是有序的,但他们的最终位置还不确定,为了给更小的元素腾出空间,他们可能会被向右移动,当索引到达数组的最右端时,排序就完成了。

代码实现

1
public class Insertion {
2
    public static void sort(Comparable[] a)
3
    {
4
        int N = a.length;
5
        for (int i = 1; i < N; i++)
6
        {
7
            //将相邻两个元素向左依次交换最终使得索引左侧的元素全部向右移动一位
8
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
9
                exch (a, j, j - 1);
10
        }
11
    }
12
}

性能分析

对随机排列长度为$N$且主键不重复的数组,平均插入排序需要$N^2/4$次比较和$N^2/4$次交换。

部分有序数组

  • 数组中每个元素距离它的最终位置都不远
  • 一个有序大数组接一个小数组
  • 数组中只有几个元素的位置不正确

插入排序对这样的部分有序数组非常有效。

希尔排序

算法描述

交换不相邻的元素对数组的局部进行排序,并最终用插入排序将局部有序数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的,这样的数组被称为h有序数组,即h个相互独立的有序数组编织在一起组成的一个数组

代码实现

1
public class Shell {
2
    public static void srot(Comparable[] a)
3
    {
4
        int N = a.length;
5
        int h = 1;
6
        while (h < N / 3)   h = 3 * h + 1;
7
        while (h > 1)
8
        {
9
            for (int i = h; i < N; i++)
10
            {
11
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
12
                    exch(a, j, j - h);
13
            }
14
            h = h / 3;
15
        }
16
    }
17
}

该希尔算法使用了序列$1/2(3^k-1)$,即序列$\{ 1,4,13 \}$,称为增量序列

性能分析

希尔排序权衡了子数组的规模和有序性,希尔排序比插入排序和选择排序快得多,并且数组越大优势越大。

归并排序

归并即将两个有序的数组归并成一个更大的有序数组。

原地归并

1
public static void merge(Comparable[] a, int lo, int mid, int hi)
2
{
3
    int i = lo, j = mid + 1;
4
    for (int k = lo; k <= hi; k++)
5
        aux[k] = a[k];
6
7
    for (int k = lo; k <= hi; k++)
8
    {
9
        if (i > mid)                      a[k] = aux[j++];
10
        else if (j > hi)                  a[k] = aux[i++];
11
        else if (less(aux[j], aux[i]))    a[k] = aux[j++];
12
        else                              a[k] = aux[i++];     
13
    }
14
}

自顶向下的归并排序

算法描述

对子数组a[lo..hi]进行排序,先将其分为$\mathrm{a}[\mathrm{lo..mid}]$和$\mathrm{a[mid+1..hi]}$两部分,分别通过递归调用将其单独排序,最后将有序的子数组归并为最终的排序结果。

1
public class Merge {
2
    private static Comparable[] aux;
3
    
4
    public static void sort(Comparable[] a)
5
    {
6
        aux = new Comparable[a.length];
7
        sort(a, 0, a.length - 1);
8
    }
9
10
    private static void sort(Comparable[] a, int lo, int hi)
11
    {
12
        if (hi <= lo)   return;
13
        int mid = lo + (hi - lo) / 2;
14
        sort (a, lo, mid);
15
        sort (a, mid + 1, hi);
16
        merge(a, lo, mid, hi);
17
    }
18
}

性能分析

对于长度为$N$的任意数组,自顶向下的归并排序需要$1/2N\lg N$至$N\lg N$次比较,最多需要访问数组$6N\lg N$次。

所以可知道归并排序所需要的时间与$N\lg N$成正比,主要缺点是辅助数组所使用的额外空间和N的大小成正比。

自底向上的归并排序

算法描述

先归并那些微型数组,然后再成对地归并得到的子数组。首先进行两两归并(把每个元素当作一个大小为1的数组),然后是四四归并(将两个大小为2的数组归并为一个有4个元素的数组),然后是八八归并,以此类推。

代码实现

1
public class MergeBU {
2
	private static Comparable[] aux;
3
    public static void sort (Comparable[] a)
4
    {
5
        int N = a.length;
6
        aux = new Comparable[N];
7
        for (int sz = 1; sz < N; sz = sz + sz)
8
        	for (int lo = 0; lo < N - sz; lo += sz + sz)
9
        		merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
10
    }
11
}

性能分析

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

快速排序

快速排序的切分

根据切分点j对数组进行切分,切分后的数组满足:

  • a[lo]a[j-1]中的所有元素都不大于a[j]
  • a[j+1]a[hi]中的所有元素都不小于a[j]
1
//切分
2
private static int partition(Comparable[] a, int lo, int hi)
3
{
4
    int i = lo, j = hi + 1;
5
    Comparable v = a[lo];
6
    while (true)
7
    {
8
        while (less(a[++i], v))
9
        {
10
            if (i == hi)    break;
11
        }
12
        while (less(v, a[--j]))
13
        {
14
            if (j == lo)    break;
15
        }
16
        if (i >= j)    break;
17
        exch(a, i, j);
18
    }
19
    exch(a, lo, j);
20
21
    return j;
22
}

基本快速排序算法

算法描述

通过递归地调用切分来进行排序。

代码实现

1
public class Quick {
2
    public static void sort(Comparable[] a)
3
    {
4
        StdRandom.shuffle(a);	//将输入乱序,消除堆输入的依赖
5
        sort(a, 0, a.length - 1);
6
    }
7
8
    private static void sort (Comparable[] a, int lo, int hi)
9
    {
10
        if (hi <= lo)   return;
11
        int j = partition(a, lo, hi);
12
        sort(a, lo, j - 1);
13
        sort(a, j + 1, hi);
14
    }
15
}

性能分析

将长度为$N$的无重复数组排序,快速排序平均需要$2N\lg N$次比较,即$1/6N\lg N$次交换。

三向切分快速排序

在含有大量重复元素时使用该方法。将数组切分为三部分,分别对应小于、等于和大于切分元素的数组元素。

代码实现

1
public class Quick3way
2
{
3
    private static void sort(Comparable[] a, int lo, int hi)
4
    {
5
        if (hi <= lo)	return;
6
        int lt = lo, i = lo + 1; gt = hi;
7
        Comparable v = a[lo];
8
        while (i <= gt)
9
        {
10
            int cmp = a[i].compareTo(v);
11
            if(cmp < 0)	exch(a, lt++, i++);
12
            else if (cmp > 0)	exch(a, i, gt--);
13
            else i++;
14
        }
15
        sort(a, lo, lt - 1);
16
        sort(a, gt + 1, hi);
17
    }
18
}

优先队列

优先队列这种数据结构应支持两种操作:

  • 删除最大元素
  • 插入元素

初级实现:有序数组、无序数组、链表

这些初级实现中,插入元素和删除最大元素的操作在最坏的情况下需要线性时间来完成,无法满足我们的性能要求。接下来使用来实现使这两种操作能更快地执行。

基于堆的优先队列

堆的定义

数据结构二叉堆满足:每个元素大于等于两个特定位置的元素,这些位置的元素又要大于等于数组中的另外两个元素,这样的数据结构可以通过有序的完全二叉树来表示。

有序的完全二叉树

在一个堆中,位置$k$的节点的父节点的位置为$k/2$,而它的两个子节点的位置为$2k$和$2k+1$。

我们可以通过计算数组的索引在树中上下移动:从$a[k]$向上一层就令$k=k/2$,向下一层则令$k=2k/2k+1$。

堆的算法

由下至上的堆有序化(上浮swim)

1
private void swim(int k)
2
{
3
    while (k > 1 && less(k/2, k))
4
    {
5
        exch(k/2, k);
6
        k = k/2;
7
    }
8
}

由上至下的堆有序化(下沉sink)

1
private void sink(int k)
2
{
3
    while (2*k <= N)
4
    {
5
        int j = 2*k;
6
        if (j < N && less(j, j+1))	j++;	//选择父节点的两个子节点中较大的作为交换对象
7
        if (!less(k, j))	break;
8
        exch(k, j);
9
        k = j;	//将交换后子节点的位置作为父节点,循环进行下一次交换,继续下沉
10
    }
11
}

基于堆的优先队列的代码实现

1
public class MaxPQ<Key extends Comparable<key>>
2
{
3
    private Key[] pq;
4
    private int N = 0;
5
    
6
    public MaxPQ(int maxN)
7
    {
8
        pq = (Key[]) new Comparable[maxN + 1];
9
    }
10
    public boolean isEmpty()
11
    {
12
        return N == 0;
13
    }
14
    public int size()
15
    {
16
        return N;
17
    }
18
    
19
    public void insert(Key v)	//在数组的末尾输入,然后进行上浮swim操作
20
    {
21
        pq[++N] = v;
22
        swim(N)
23
    };
24
    
25
    public Key delMax()
26
    {
27
        Key max = pq[1];
28
        exch(1, N--);
29
        pq[N++] = null;
30
        sink(1);
31
        return max;
32
    }
33
}

基于堆的优先队列性能分析

优先队列性能分析

堆排序

堆的构造

高效的构造堆的方法是从右向左用sink()函数构造子堆。数组的每个位置都是一个子堆的根结点,如果一个结点的两个子结点都已经是堆了,那么在该结点上调用sink()可以将它们变成一个堆。我们只需要扫描一半的元素,因为可以跳过大小为1的子堆。

堆的构造

下沉排序

将堆中的最大元素删去,然后将其放入堆缩小后数组中空出的位置。

堆排序代码实现

1
public static void sort(Comparable[] a)
2
{
3
    int N = a.length;
4
    for (int k = N/2; k >= 1; k--)	//构造堆
5
        sink(a, k, N);
6
    while (N > 1)
7
    {
8
        exch(a, 1, N--);	//堆排序,按递减顺序循环取出所有的最大值,最后得到排序结果。
9
        sink(a, 1, N);
10
    }
11
}

堆排序性能分析

将$N$个元素排序,堆排序只需要少于$(2N\lg N+2N)$次比较以及一半的交换次数。