Rooki3Ray | Cyber Security
0%

《algorithm》之排序与查找

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 12 分钟

拜读《Algorithms》，主要阅读了排序和查找算法。

基础

基础编程模型

Java程序的基本结构

一段Java程序（类）或是一个静态方法（函数）库，或是定义了一个数据类型。用到以下语法：

  • 原始数据类型
  • 语句：声明、赋值、条件、循环、调用、返回
  • 静态方法：可以封装并重用代码，便于用独立模块开发程序
  • 字符串
  • 标准I/O
  • 数据抽象：数据抽象封装和重用，便于定义非原始数据类型，进而支持面向对象编程

数据抽象

数据类型指一组值和一组对这些值的操作的集合。

Java编程的基础主要是使用class关键字构造引用类型的数据类型——面向对象编程。抽象数据类型（ADT）可以对使用者隐藏数据表示的数据类型。

使用抽象数据类型

抽象数据类型的API

用API来说明抽象数据类型的行为，列出所有构造函数和实例方法。

抽象数据类型的定义和静态方法库之间的不同：

  • API可能会出现若干个名称与类名相同且无返回值的函数，即构造函数
  • 实例方法不需要static关键字，不是静态方法
  • 某些实例方法是继承的方法

继承的方法

任何数据类型都能通过在API中包含特定的方法从Java的内在机制中获益。

对象

对象是能够承载数据类型的值的实体。

三大特性：状态、标识和行为。状态即数据类型中的值，标识可以认为是在内存中的位置，行为即数据类型的操作。

引用是访问对象的一种方式，Java使用术语引用类型以表示和原始数据类型的区别。

创建对象

new+类名+(paras)来触发构造函数。调用new时系统会：

  • 为新对象分配内存空间
  • 调用构造函数初始化对象中的值
  • 返回该对象的一个引用

调用实例方法

对象变量名.实例方法名(paras)

方法的每次触发都是和一个对象相关的，通过触发一个实例方法可以操作对象的值。

静态方法调用的开头是类名（通常为大写），而实例方法调用的开头是对象名（通常为小写）。

使用对象

声明以引用对象、用关键字new触发该类型的对象的构造函数、使用变量名调用实例方法。

可以像使用原始数据类型的变量一样使用和对象关联的变量。

赋值语句

使用引用类型的赋值语句会创建该引用的一个副本，赋值并不会创建新的对象，而是创建一个引用，即别名。

将对象作为参数

当调用一个需要参数的方法时，每个参数名都相当于左值，而传入的参数值相当于右值，即将参数值的一个副本从调用端传递给方法——按值传递。但使用引用类型参数时，传入的都是对象的引用，能够改变对象的值。

将对象作为返回值

用对象就可以返回多个值

数组也是对象

所有非原始数据类型的值都是对象，数组、字符串也是。

对象的数组

  • 使用方括号语法调用数组的构造函数创建数组
  • 对每个数组元素调用它的构造函数创建相应的对象

数据类型的设计

封装

模块化编程

设计API

应该以能够复用的方式编写每个程序，API应该能够清楚地说明所有可能的输入和副作用。

接口继承

Java为定义对象之间的关系提供了支持——接口。

子类型（第一种继承机制）允许通过指定一个含有一组公共方法的接口为两个本来并没有关系的类建立一种联系，这两个类都必须实现这些方法。这种方式称为接口继承。

实现继承

子类的主要思想是定义一个新类（子类或派生类）来继承另一个类的所有实例方法和实例变量。

封装类型

Java提供了一些内置的引用类型：Boolean、Byte、Character、Double、Float、Integer、Long、Short，含有继承得到的实例方法，在需要时Java会自动将原始数据类型转换为封装类型。

等价性

equals()必须是一种等价性关系：

  • 自反性
  • 对称性
  • 传递性
  • 一致性
  • 非空性

内存管理

Java最重要的一个特性就是自动内存管理，通过记录孤儿对象并将他们的内存释放到内存池中来回收内存——垃圾回收。

Java不允许修改引用的策略。

不可变性

不可变数据类型：该类型的对象中的值创建后无法改变。

Java通过final修饰符来强制保证不可变性，只能通过赋值语句和构造函数赋值一次，但final仅可用于保证原始数据类型的实例变量的不可变性，而无法用于引用类型的变量（会使引用无法改变，永远指向同一个对象，但对象的值仍是可变的）。

契约式设计

能够在程序运行时检验程序状态的一些机制：

  • 异常（Exception）：一般用于处理不受控制的不可预见的错误
  • 断言（Assertion）：验证在代码中做出的一些假设

异常与错误

都是程序运行中出现的破坏性事件，Java采取的行动称为抛出异常或抛出错误，也可以创建自己的异常。

1
throw new RuntimeException("Error message here.")

断言

断言是一条需要在程序的某处确认为true的布尔表达式，如果为false程序将会终止并报告出错信息。

使用断言来确定程序的正确性并记录编程意图，使用断言来保证代码永远不会被系统错误终止或进入死循环。

背包、队列和栈

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Bag<Item> implements Iterable<Item>
    		Bag()				创建一个空背包
        void add(Item item)   	  添加一个元素
     boolean isEmpty()		 	 背包是否为空
    	 int size()			 	 背包中的元素数量
    
public class Queue<Item> implements Iterable<Item>
    		Queue()				创建空队列
    	void enqueue(Item item)	  添加一个元素
    	Item dequeue()			 删除最近添加的元素
     boolean isEmpty()			  队列是否为空
    	 int size()				 队列中的元素数量
    
public class Stack<Item> implements Iterable<Item>
    		Stack()				创建空栈
    	void push(Item item)	 添加一个元素
    	Item pop()		 	 	删除最近添加的元素
     boolean isEmpty()		 	 栈是否为空
    	 int size()				栈中的元素数量

泛型

集合类的抽象数据类型的一个关键特性是可以用他们存储任意类型的数据。Java的泛型机制（参数化类型）能够做到这一点。在每个API中，类名后的\记号将Item定义为一个类型参数，它是一个象征性的占位符，表示用例将会使用的某种具体数据类型。创建栈时可以将Item替换为任意引用数据类型。

自动装箱

类型参数必须被实例化为引用类型，因此Java有一种特殊机制来使泛型代码能够处理原始数据类型，Java会自动在引用类型和对应的原始数据类型之间进行转换（自动装箱、自动拆箱）。

可迭代的集合类型

大部分应用场景下的要求只是用某种方式处理集合中的每个元素，或者叫迭代访问集合中的所有元素。

1
2
for (Transaction t : collection)
{	StdOut.println(t);	}

背包

背包是一种不支持从中删除元素的几何数据类型——他的目的就是帮助用例收集元素并迭代遍历所有收集到的元素，迭代顺序不确定且与用例无关。使用Bag就说明元素的处理顺序并不重要。

FIFO队列

队列是基于FIFO策略的集合类型。使用队列的原因是保存元素的同时保存他们的相对顺序。用例使用foreach语句迭代访问队列中的元素时，元素的处理顺序就是他们被添加到队列中的顺序。

下压栈

下压栈是基于LIFO的集合类型。用例使用foreach语句迭代访问栈中的元素时，元素的处理顺序与它们被压入栈的正好相反。

集合数据类型的实现

在pop()时，将元素值设为null，可以防止对象游离。

迭代器需要实现hasNext()和next()方法。

1
2
3
4
5
6
public interface Iterator<Item>
{
    boolean hasNext();
    Item next();
    void remove();
}

链表

链表是一种递归的数据结构，它或者为null，或者指向一个node的引用，该节点还有一个泛型的元素和一个指向另一条链表的引用。

数组和链表是两种表示对象集合的方式——顺序存储和链式存储。

结点记录

用一个嵌套类来定义结点的抽象数据类型。

1
2
3
4
5
private class Node
{
    Item item;
    Node next;
}

从表头插 入结点

1
2
3
4
Node oldfirst = first;
first = new Node();
first.item = "new";
first.next = oldfirst;

从表头删除结点

1
first = first.next

在表尾插入结点

需要一个指向链表尾结点的链接，这个链接必须被修改并指向一个含有新元素的结点，维护一个额外的链接并不可取，因为修改链表的操作可能需要修改该变量。

1
2
3
4
Node oldlast = last;
last = new Node();
last.item = "new";
oldlast.next = last;

其他位置的插入与删除

  • 删除指定的结点
  • 在指定结点前插入一个新结点

实现任意插入和删除操作的标准解决方案是双向链表。

遍历

1
2
3
4
for (Node x = first; x != null; x = x.next)
{
    // 
}

栈的实现

将栈保存为一条链表，栈顶为表头。push即在表头添加元素，pop即删除表头元素。

队列的实现

将队列保存为一条链表，队列开头为表头。enqueue即在表尾添加元素，dequeue即删除表头元素。

背包的实现

将stack中的push改为add，并去掉pop即可。

算法分析

时间

得到运行时间的数学模型所需的步骤：

  • 确定输入模型，定义问题的规模
  • 识别内循环
  • 根据内循环中的操作确定成本模型
  • 对于给定的输入，判断这些操作的执行频率

内存

  • 对象：所有实例变量的内存+对象本身的开销16bytes（内存的使用一般会被填充为8bytes）
  • 链表：需要8bytes额外开销
  • 数组：24bytes头信息=16bytes对象开销+4bytes保存长度+4bytes填充字节
  • 字符串对象：对象的16bytes+指向字符数组的引用8bytes+描述的字符数组中的偏移量4bytes int+计数器（字符串长度）的4bytes int+散列值4bytes int+4bytes填充字节
  • 字符串的值和子字符串：String的40bytes+字符数组的24+2N bytes

Union-Find（并查集）算法

并查集算法是解决动态连通性问题的高效数据结构。

动态连通性

问题的输入是一列整数对，每个整数都表示一个对象，整数对p和q表示p和q是相连的，这是一种对等的关系。

  • 网络中是否需要建立新的通路
  • 编程环境中变量名（引用）是否等价
  • 数学集合的抽象问题

API设计

触点和分量都用int表示，则可以用一个以触点为索引的数组id[]来表示所有分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class UF
{
    private int[] id;
    private int count;
    public UF(int N)
    {
     	count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    public int count()
    {	return count;	}
    public boolean connected(int p, int q)
    {	return find(p) == find(q);	}
    public int find(int p)
    public void union(int p, int q)
}

quick-find算法

一种方法是保证同一连通分量的触点在id[]中的值全部相同。在调用union时，如果p和q不在同一分量中，需要将q所在的分量的所有触点的id[]均置为id[p]。

1
2
3
4
5
6
7
8
9
10
11
12
public int find(int p)
{	return id[p];	}
public void union(int p, int q)
{
    int pID = find(p);
    int qID = find(q);
    if (pID == qID) return;
    
    for (int i = 0; i < id.length; i++)
        if (id[i] == pID) id[i] = qID;
    count--;
}

需要扫描整个id[]数组，find仅访问数组1次，union操作访问数组 N+3到2N+1 次，那么最坏情况下至少需要(N-1)(N+3)次。

quick-union算法

id[]数组值为同一分量中另一触点的名称，这种联系称为链接，根触点就是链接指向自己的触点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int find(int p)
{
    while (p != id[p]) p = id[p];
    return p;
}
public void union(int p, int q)
{
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) return;
    
    id[pRoot] = qRoot;
    count--;
}

链接的结构实际上是树，id数组用父链接表示了森林，find中返回root从而判断两节点是否在同一棵树，而在union中通过将一个root变为另一个root的父节点，归并了两棵树。

find需要访问数组1到2N-1次，并不总是线性复杂度，相比quick-find算法有所改进。

最坏情况下输入为0-1，0-2，……，0-(N-1)，每个输入对0-i需要访问数组2i+2次

加权quick-union算法

记录每棵树的大小并在每次union中将小树连接到大树上

在类中添加一个sz[]数组记录各个根节点所对应的分量大小。

最坏情况下，union合并的树大小总是相同，能够保证lgN级别的性能。

对于N个触点，加权q-u算法构造的森林中任意节点的深度最多为log N

对于加权q-u算法和N个触点，最坏情况下connect、find、union的复杂度为log N

路径压缩的加权quick-union算法

在find中添加一个循环，将路径上的节点都直接链接到根节点。

排序

初级排序算法

选择排序

不断选择元素中的最小者与第一个元素交换位置，交换的次数为N，比较的次数为1+2+3+…+(N-1)~ $N^2/2$。

  • 运行时间和输入的状态（是否有序）无关
  • 数据移动最少——只有N次交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Java
public class Selection
{
    public  static void sort(Comparable [] a)
    {
        int N = a.length;
        for (int i = 0; i < N; i++)
        {
            min = i;
            for (int j = i+1; j < N; j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        }
    }
}
1
2
3
4
5
6
7
8
9
# Python
class Selection():
    def sort(a: list):
        for i, num in enumerate(a):
            min = i
            for j in range(i, len(list)):
                if a[j] < a[min]:
                    min = j
            a[min], a[i] = a[i], a[min]

插入排序

将每个元素插入到已经有序的序列中。最坏情况下需要$N^2/2$比较和交换，最好情况下需要N-1次比较和0次交换。

  • 运行时间与输入的状态有关。
1
2
3
4
5
6
7
8
9
10
11
12
13
// Java
public class Insertion
{
    public static void sort(Comparable [] a)
    {
        int N = a.length;
        for (int i = 0; i < N; i++)
        {
            for(int j = i; j > 0 && less(a[j], a[j-1]); j--)
                exch(a, j, j-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
# Python
class Insertion():
    def sort(a: list):
        for i, num in enumerate(a):
            j = i
            for j in range(i, 0, -1):
                if a[j] >= a[j-1]:
                    break
                a[j], a[j-1] = a[j-1], a[j]

插入排序对部分有序数组很有效（特别是倒置的数目很少时）：

  • 数组中每个元素距离其正确位置不远
  • 一个有序大数组接小数组
  • 数组中仅有几个元素位置不正确

希尔排序

基于插入排序的算法，交换不相邻的元素对数组局部排序，并最终用插入排序将局部有序的数组排序。

h有序数组：数组中任意间隔为h的元素都是有序的。

对每个h，用插入排序将h个子数组独立的排序，再减小h直到h=1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Java
public class Shell
{
    public static void sort(Comparable [] a)
    {
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3 * h + 1;
        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], a[j-h]);
            }
            h = h/3;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Python
class Shell():
    def sort(a: list):
        h = 1;
        while h < N/3:
            h = 3 * h + 1
        while h >= 1:
            for i, num in enumerate(a):
                j = i
                for j in range(i, 0, -h):
                    if a[j] >= a[j-h]:
                        break
                    a[j], a[j-1] = a[j-1], a[j]
            h = h / 3

归并排序

归并排序时间复杂度为O(Nlg N)，但需要额外O(N)的空间。

原地归并的抽象方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Java 原地归并的抽象方法
 public static 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 (less(aux[i], aux[j])) a[k] = aux[i++];
         else a[k] = aux[j++];
     }
 }

自顶向下的归并排序

分治思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Merge
{
    private static Comparable[] aux;
    public static void merge(Comparable [] a, int lo, int mid, int hi)
    public static void sort(Comparable [] a)
    {
        aux = new Comparab1e[a.length];
        sort(a, 0, a.length - 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);
    }
}
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
# Python
class Merge():
    def merge(self, a: list, lo: int, mid: int, hi: int):
        i = lo
        j = mid +1
        aux = a[:] # copy list (or a[:], a*1, copy.copy(a) )
        for k in range(lo, hi+1):
            if i > mid:
                a[k] = aux[j]
                j += 1
            elif j > hi:
                a[k] = aux[i]
                i += 1
            elif aux[i] < aux[j]:
                a[k] = aux[i]
                i += 1
            else:
                a[k] = aux[j]
                j += 1
    def __sort__(self, a: list, lo: int, hi: int):
        if hi <= lo:
            return
        mid = int(lo + (hi - lo) / 2 )
        self.__sort__(a, lo, mid)
        self.__sort__(a, mid+1, hi)
        self.merge(a, lo, mid, hi)
    def sort(self, a: list):
        self.__sort__(a, 0, len(a)-1)

N个元素的数组最多构成$n=lgN$层的树，自顶向下的第k层有$2^k$个子数组，每个数组长度为$2^{n-k}$即最多比较次数，故每层最多比较$2^n$次，那么n层一共比较至多$2^n*n=NlgN$次。

对于长度为N的数组，自顶向下的归并排序需要$NlgN/2 至 NlgN$次比较；最多需要访问数组$6NlgN$次（$2N复制 2N移动 至多2N比较$）。

  • 小数组使用插入排序
  • 提前测试mid小于等于mid+1
  • 不将元素复制到辅助数组（而是直接排序到）

自底向上的归并排序

先归并微型数组，自底向上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Java
public class MergeBU
{
    private static Comparable[] aux;
    // merge()方法
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = 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))
        }
    }
}

N为2的幂时，自底向上和自顶向下的比较与访问次数相同。

自底向上方法适合链表组织的数据，只需重新组织链表链接即可原址排序。

复杂度

  • 基于比较的算法比较次数不可能小于$lg(N!)$~$NlgN$。
  • 归并排序时渐进最优的基于比较的排序算法。

快速排序

优点：

  • 原址排序（仅需小辅助栈）
  • $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
30
// Java
public class Quick
{
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);	// 消除对输入的依赖
        sort(a, 0, a.length-1);
    }
    private static 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;
    }
    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);
    }
}

先调用partition()将a[j]的位置排定，之前的元素不大于它，之后的元素不小于它。

切分过程：

  • 随机选取a[lo]作为切分元素
  • 分别从左和从右开始扫描数组，寻找未排定的元素交换位置
  • 指针相遇时交换切分元素和左子数组最右侧元素即可

性能特点

平均情况：比较次数$C_N = 2C_{N/2}+N$，即$2NlnN=1.39NlgN$

最坏情况：$N^2/2$次比较，但可以通过shuffle预防。

比较次数多于归并排序，但移动次数少。

算法改进

  • 对小数组使用插入排序
  • 用三取样的中位数切分
  • 三向切分：维护三个指针（大于、小于、等于）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Java
public class Quick3way
{
    private static 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);
    }
}

优先队列

某些分配调度场合下只需要支持两种操作：删除最大元素 和 插入元素

仅维护大小为M的优先队列即可。

初级实现方法

  • 无序数组（delete时类似选择排序找到最大元素）
  • 有序数组（insert时做插入排序，最大元素始终在一边）
  • 链表

堆

二叉树的父节点大于等于两个子节点——堆有序。

位置$k$的结点的父节点位置为$\lfloor k/2 \rfloor$，子节点为$2k$和$2k+1$。

1
2
3
4
5
6
// Java
/* pq[]长度为N+1，不使用pq[0]*/
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;	}

由下至上的堆有序化（上浮）

某节点变得比父节点大，有序状态被打破。将该节点与父节点交换，不断上移。

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

由上至下的堆有序化（下沉）

某个节点变得比子节点小，有序状态被打破。将该节点和两个子节点中较大者交换，不断下移。

1
2
3
4
5
6
7
8
9
10
11
12
// Java
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;
    }
}
  • 插入元素：插入到数组末尾，不断上浮到合适位置
  • 删除最大元素：删除最大元素（根节点）并将数组的最后一个元素放到根节点，不断下沉到合适位置。

整体实现

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
// Java
public class MaxPQ<Key extends Comparable <key>>
{
    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;	}
    public void insert(Key v)
    {
        pq[++N] = v;
        swim(N);
    }
    public void delMax()
    {
        Key max = pq[1];
        exch(1, N--);
        pq[N+1] = null;	//防止越界
        sink(1);
        return max;
    }
    private boolean less(int i, int j);
    private void exch(int i, int j);
    private void swim(int k);
    private void sink(int k);
}
  • insert 不超过$lgN+1$次比较
  • delMax不超过$2lgN$次比较

其他改进

多叉堆

需要在树高（$log_d N$）和从每个结点的$d$个子结点中找到最大者的代价之间折中

调整数组大小

像栈实现一样insert中添加长度加倍、delMax添加长度减半

元素的不可变性

假设用例代码不会改变元素

索引优先队列

允许用例引用优先队列中的元素——给每个元素一个索引。

堆排序

将所有元素插入一个查找最小元素的优先队列，重复调用delMin()方法按顺序删去即可排序。

堆的构造

  • 从左到右swim()保证指针左侧堆有序（类似insert）
  • 从右到左sink()构造子堆，

构造堆只需要少于2N次比较和少于N次交换

1
2
3
4
5
6
7
8
9
10
11
12
// Java
public static void sort(Comparable[] a)
{
    int N = a.length;
    for (int k = N/2; k >= 1; k--)
        sink(a, k, N);	// 表示将a[]从a[k]到a[N]排序
    while (N > 1)
    {
        exch(a, 1, N--);
        sink(a, 1, N);
    }
}

下沉排序

每次删除最大元素，放入堆缩小后数组空出的位置。

堆排序需要少于$2NlgN+2N$次比较和一半次数的交换

先下沉后上浮

？？？并不能理解

堆排序的特点

在排序复杂性的研究中很重要，唯一能够同时最优利用空间和时间的方法——最坏情况下用~$2NlgN$次比较和恒定的额外空间。

  • 在空间紧张的嵌入式操作系统和移动设备中经常使用；现代操作系统很少使用，因为无法利用缓存，元素很少和相近的元素比较，miss的次数远大于hit。
  • 能在插入和删除最大元素操作的动态场景中保证对数级别的运行时间。

总结

排序算法的稳定性：能够保留数组中重复元素的相对位置

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

查找

二分查找

image-20210227192335974

二叉查找树

在二叉树中，每个结点只能有一个父结点（根节点除外），每个结点都有左右两条链接，分别指向一棵子二叉树或空。

同一个集合可以用多棵不同的二叉查找树表示。

查找

递归查找：

  • 树为空，则miss；
  • 和当前结点的键相同，则hit；
  • 和当前结点的键不同，则递归地到子树中查找。
1
2
3
4
5
6
7
8
9
10
11
// Java
public Value get(Key key)
{	return get(root, key);	}
private Value get(Node x, Key key)
{
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) return get(x.left, key);
    else if (cmp > 0) return get(x.right, key);
    else return x.val;
}

插入

递归插入：

  • 树为空，则返回一个含有该键值对的新结点；
  • 小于当前结点的键，则在左子树递归插入；
  • 大于当前结点的键，则在右子树递归插入。
1
2
3
4
5
6
7
8
9
10
11
12
13
// Java
public void put(Key key, Value val)
{	root = put(root, key, val);	}
private Node put(Node x, Key key, Value val)
{
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else x.val = val;
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

分析

二叉查找树的运行时间取决于树的形状，而树的形状取决于结点插入的顺序。

二叉查找树和快速排序的思想相似。

N个结点的二叉查找树中，查找命中所需的比较次数平均为~$2lnN(1.39lgN)$，插入和查找未命中所需的比较次数平均也为~$2lnN(1.39lgN)$（仅多1次额外比较）。

删除

在删除结点x后用其后继节点填补位置。

  • 将指向即将被删除的节点的链接保存为t
  • 将x指向后继结点min(t.right)
  • 将x的右链接指向deleteMin(t.right)
  • 将x的右链接指向t.left

范围查找

中序遍历：递归查找根节点的左子树，然后查找根节点，再查找根节点的右子树。

性能

  • 二叉查找树的所有操作在最坏情况下所需时间都和树高成正比
  • 随机键构造的二叉树高趋近于$2.99lgN$

平衡查找树

2-3查找树

  • 2-结点：含有一个键和两条链接
  • 3-结点：含有两个键和三条链接

你可以打赏我哦！