0%

LEC 1 概述

解决问题的三要素:输入 输出 算法

数据结构

输入、输出与数据结构直接相关。

数据结构时数据之间的逻辑关系、数据在计算机上的存储方式、数据的操作。

数据结构与算法设计是密切相关的。

算法

算法是为了求解问题而给出的指令序列。

一般特性

正确性
有效性
确定性
有穷性

算法效率

计算时间
存储空间
网络带宽

LEC 2 算法渐进分析

一般我们不必花大力气算出算法的精确运行时间,我们关心的是在大规模的输入下,算法的运行时间是如何随着输入规模的增大而变化的。此时,我们可以忽略低阶项和常量,使用渐进分析。
开销函数的估计是相对的而不是绝对的,开销函数的阶的增长决定了开销的大小。

渐进符号

$O$ 渐进上界
$Ω$ 渐进下界
$Θ$ 渐进紧确界

分析实例

矩阵求和

$O(n)$ $n=k^2$ (k 为矩阵维度)

插入排序

最好 O(n) 最坏 O(n^2)

合并排序

$O(nlgn)$

LEC 3 递归关系

许多算法,时间开销函数都可以用递归关系来描述。

置换法

猜想出一个表达式,验证表达式的正确性。

递归树

将迭代过程展成树的形式,分析树的每一层的消耗,然后求和。

迭代法

根据迭代公式,利用数学方法求解。

主方法

主方法依赖如下的主定理:

可以根据主定理方便求解效率,但有真空地带。

LEC 4 线性时间的排序法

基于比较的排序的开销下限

这一节先分析了基于比较的方法的排序的开销下限,我们通过判定树模型证明下限为$nlgn$。要打破这个下限,就要寻找非比较的排序方法,即:

计数排序

基本思想是排序指定范围内(0~k)的数,使用大小分别为n、k、n的数组a、b、c。根据 c 中小于 x 的个数,将元素放到 b 的指定位置。

基数排序

基本思想是根据数字每一位的大小进行排序。

桶排序

基本思想是将待排序元素放入桶中,每个桶分别排序,桶之间保持顺序。

LEC 5 分治法

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

应用

二分搜索

归并排序

最大子数组问题

矩阵乘法的 Strassen 算法

Strassen 算法的运行时间的递归式为:

$T(n)=7T(n/2)+Θ(n^2)$

这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。

最近点对算法

最近点对算法的递归式为:

$T(n)=2T(n/2)+O(n)$

这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。

LEC 6 随机化算法

雇佣关系

快速排序

随机化算法的分类

Las Vegas 算法 :总能给出正确的解或者无解。

Monte Carlo 算法 :大多数给出正确解,错误率可以控制在一定程度上。

如检查两个长串是否相同,直接比较为 Las Vegas 算法,验证指纹则为 Monte Carlo 算法。

LEC 7 统计算法

LEC 8 动态规划

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。

LEC 9 贪心算法

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

(2)证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

LEC 10 图算法

图的表示和存储方式

邻接链表 邻接矩阵

邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。

在稠密图的情况下,我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连,可能也需要使用邻接矩阵表示法。

LEC 11 最小生成树

LEC 12 单源最短路径

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

LEC 13 全成对最短路径

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。

排序方法 平均时间复杂度 最坏时间复杂度
插入排序 $O(n^2)$ $O(n^2)$
合并排序 $O(nlgn)$ $O(nlgn)$
快速排序 $O(nlgn)$​ $O(n^2)$
随机快速排序 $O(nlgn)$ -
计数排序 $O(n+k)$ -
基数排序 $O(d(n+k))$ $O(d(n+k))$
桶排序 $O(n)$ -

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。

图的表示和存储方式

邻接链表 邻接矩阵

邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。

在稠密图的情况下,我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连,可能也需要使用邻接矩阵表示法。

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

(2)证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

分析分治算法

应用

归并排序

最大子数组问题

矩阵乘法的 Strassen 算法

Strassen 算法的运行时间的递归式为:

$T(n)=7T(n/2)+Θ(n^2)$

这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。

最近点对算法

最近点对算法的递归式为:

$T(n)=2T(n/2)+O(n)$

这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。

数据结构研究组织大量数据的方法,算法分析则是对算法运行时间的评估。

算法是为求解一个问题需要遵循的、被清除地指定的简单指令的集合。

数据结构在计算机科学界至今没有一个标准的定义

普遍认可的算法的定义:算法是解决特定问题求解步骤的描述。

算法的特性:

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

引论

  • 数学知识

    级数:

  • 证明方法

    • 归纳法
    • 反证法
  • 递归简论

    • 设计递归的基本法则:
      1. 基准情形
      2. 不断推进
      3. 设计效益:假设所有的递归调用都能运行。
      4. 合成效益法则:不要做重复性工作。

算法分析

  • 数学基础

    $O(f(N))$ 上限

    $Ω(f(N))$ 下限

    $Θ(f(N))$ 相等

    $o(f(N))$ 小于

表、栈和队列

    • 数组
    • 链表
  • 中缀表达式转换为后缀表达式:

    中缀表达式可以通过栈转换成后缀表达式,P54

后缀表达式转换成表达式树同样借助栈:P71

扫描后缀表达式,若遇到operator,构造单节点树,入栈;

若遇到operand,从栈中弹出两棵树,以operand为根,合并弹出的两棵树,将得到的树入栈

时间复杂度=表达式的长度

  • 队列

    1
    2
    3
    4
    5
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    • CreateQueue()
    • IsFull()
    • IsEmpty()
    • Enqueue()
    • Dequeue()
    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
    63
    64
    65
    66
    67
    68
    69
    // 队列的数组实现
    // Created by aoyun on 2019/11/24.
    //
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>

    #define ERROR -1

    typedef int ElementType;
    typedef int Position;
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    typedef struct QNode *Queue;

    static Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue) malloc(sizeof(struct QNode));
    Q->Data = (ElementType *) malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = -1; // ZJU代码有错
    Q->MaxSize = MaxSize;
    return Q;
    }

    static bool IsFull(Queue Q) {
    return ((Q->Rear + 1) % Q->MaxSize == Q->Front);
    }

    /**
    *
    * @param Q
    * @param X
    * @return 是否入队成功,队列已满会失败
    */
    static bool AddQ(Queue Q, ElementType X) {
    if (IsFull(Q)) {
    printf("队列满");
    return false;
    } else {
    Q->Rear = (Q->Rear + 1) % Q->MaxSize; // 队尾向后移
    Q->Data[Q->Rear] = X;
    return true;
    }
    }

    static bool IsEmpty(Queue Q) {
    return (Q->Front == Q->Rear);
    }

    ElementType DeleteQ(Queue Q) {
    if (IsEmpty(Q)) {
    printf("队列空");
    return ERROR;
    } else {
    Q->Front = (Q->Front + 1) % Q->MaxSize;
    return Q->Data[Q->Front];
    }
    }

    int main() {
    Queue Q = CreateQueue(4);
    AddQ(Q, 1);
    AddQ(Q, 2);
    AddQ(Q, 3);
    AddQ(Q, 4);
    printf("\n%d", DeleteQ(Q));
    }

  • 二叉树

    最多两个子节点

  • 二叉查找树

    每一个根节点,左子树的所有元素比根节点小,右子树相反。

  • AVL树

    有条件的平衡树

  • 伸展树

  • 树的遍历

  • B-树

    在2m阶B树中关键码个数n与B树高度h之间的关系为 $h≤log_m((n+1)/2)+1$

散列

  • 散列函数
  • 分离链接法
  • 开放定址法
  • 再散列
  • 可扩散列

优先队列

  • 二叉堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*----------- 建造最大堆 -----------*/
    /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
    void PercDown(MaxHeap H, int p) {
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; /* 取出根结点存放的值 */
    for (Parent = p; Parent * 2 <= H->Size;) {
    Child = Parent * 2;
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
    Child++; /* Child指向左右子结点的较大者 */
    if (X >= H->Data[Child])
    break; /* 找到了合适位置 */
    else /* 下滤X */
    H->Data[Parent] = H->Data[Child];
    Parent = Child;
    }
    H->Data[Parent] = X;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void MaxDown(MaxHeap H, int p) {
    int Parent, Child; // Parent-父节点在数组中的指针 Child-子节点在数组中的指针
    int X;
    X = H->Data[p];
    for (Parent = p; Parent * 2 < H->Size;) { // 从上往下,找p的正确位置
    Child = Parent * 2; // Child在Parent*2处
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) {
    Child++; // 找到较大的Child
    }
    if (X > H->Data[Child]) { // p就是正确位置
    break;
    } else { // 子节点更大,把子节点数值赋值到父节点位置
    H->Data[Parent] = H->Data[Child];
    }
    Parent = Child; // 父节点转到Child位置,重新开始新的一轮寻找父节点正确位置的过程
    }
    H->Data[Parent] = X;
    }
  • 应用

  • d-堆

  • 左式堆

  • 斜堆

  • 二项队列

排序

  • 冒泡排序

  • 选择排序

  • 插入排序

    向扑克牌一样,把新元素插入到正确的位置

  • 希尔排序

    缩小增量的插入排序

  • 堆排序

    1. 堆的构造
    2. 下沉排序

    利用堆的性质进行排序

  • 归并排序

    分治。先分,分成小单位;再治,对小单位排序;最后合并。

  • ==快速排序==

  • 桶排序

    知道元素的范围

  • 基数排序

    次位优先

  • 表排序

    大型结构的排序,移动不能

  • 外部排序

屏幕截图_216_.png

不相交集

图论算法

  • 定义
  • 拓扑排序
  • 最短路径
    • Dijkstra算法 单源最短路径
    • Floyd算法 多源最短
  • 网络流
  • 最小生成树
    • Prim
    • Kruskal
  • 深度优先搜索
  • NP-完全性

算法设计技巧

  • 贪婪算法

  • 分治算法

  • 动态规划

    核心思想:

    将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

  • 随机化算法

  • 回溯算法

更多

广度优先搜索

复杂度总结

  • BuildHeap
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
//
// Created by aoyun on 2019/11/24.
//
#include <stdlib.h>
#include <stdio.h>

#define ElementType int

/**
* <p>插入排序</p>
* 把元素插到正确的位置
* @param A 待排序数组
* @param N 数组元素个数
*/
static void InsertionSort(ElementType A[], int N) { /* 插入排序 */
int P, i;
ElementType Tmp;

for (P = 1; P < N; P++) {
Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
for (i = P; i > 0 && A[i - 1] > Tmp; i--) /*从后向前*/
A[i] = A[i - 1]; /*依次与已排序序列中元素比较并右移*/
A[i] = Tmp; /* 放进合适的位置 */
}
}

/**
* <p>希尔排序</p>
*
* @param A
* @param N
*/
void ShellSort(ElementType A[], int N) { /* 希尔排序 - 用Sedgewick增量序列 */
int Si, D, P, i;
ElementType Tmp;
/* 这里只列出一小部分增量 */
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

// 找到合适的初始增量
for (Si = 0; Sedgewick[Si] >= N; Si++); /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
for (P = D; P < N; P++) { /* 插入排序*/
Tmp = A[P];
for (i = P; i >= D && A[i - D] > Tmp; i -= D)
A[i] = A[i - D];
A[i] = Tmp;
}
}

void Swap(ElementType *a, ElementType *b) {
ElementType t = *a;
*a = *b;
*b = t;
}

static void PercDown(ElementType A[], int p, int N) { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;

X = A[p]; /* 取出根结点存放的值 */
for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
Child = Parent * 2 + 1;
if ((Child != N - 1) && (A[Child] < A[Child + 1]))
Child++; /* Child指向左右子结点的较大者 */
if (X >= A[Child]) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}

/**
* 利用堆的特性排序
* @param A
* @param N
*/
void HeapSort(ElementType A[], int N) { /* 堆排序 */
int i;

for (i = N / 2 - 1; i >= 0; i--)/* 建立最大堆 */
PercDown(A, i, N);

for (i = N - 1; i > 0; i--) {
/* 删除最大堆顶 */
Swap(&A[0], &A[i]); /* 见代码7.1 */
PercDown(A, 0, i);
}
}

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void
Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;

LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;

while (L <= LeftEnd && R <= RightEnd) {
if (A[L] <= A[R])
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}

while (L <= LeftEnd)
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while (R <= RightEnd)
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

for (i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd) { /* 核心递归排序函数 */
int Center;

if (L < RightEnd) {
Center = (L + RightEnd) / 2;
Msort(A, TmpA, L, Center); /* 递归解决左边 */
Msort(A, TmpA, Center + 1, RightEnd); /* 递归解决右边 */
Merge(A, TmpA, L, Center + 1, RightEnd); /* 合并两段有序序列 */
}
}

void MergeSort(ElementType A[], int N) { /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *) malloc(N * sizeof(ElementType));

if (TmpA != NULL) {
Msort(A, TmpA, 0, N - 1);
free(TmpA);
} else printf("空间不足");
}

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length) { /* 两两归并相邻有序子列 */
int i, j;

for (i = 0; i <= N - 2 * length; i += 2 * length)
Merge(A, TmpA, i, i + length, i + 2 * length - 1);
if (i + length < N) /* 归并最后2个子列*/
Merge(A, TmpA, i, i + length, N - 1);
else /* 最后只剩1个子列*/
for (j = i; j < N; j++) TmpA[j] = A[j];
}

void Merge_Sort(ElementType A[], int N) {
int length;
ElementType *TmpA;

length = 1; /* 初始化子序列长度*/
TmpA = malloc(N * sizeof(ElementType));
if (TmpA != NULL) {
while (length < N) {
Merge_pass(A, TmpA, N, length);
length *= 2;
Merge_pass(TmpA, A, N, length);
length *= 2;
}
free(TmpA);
} else printf("空间不足");
}

/**
* 前中后3值选出pivot
* @param A
* @param Left
* @param Right
* @return
*/
ElementType Median3(ElementType A[], int Left, int Right) {
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right - 1]; /* 返回基准Pivot */
}

void Qsort(ElementType A[], int Left, int Right) { /* 核心递归函数 */
int Pivot, Cutoff, Low, High;

if (Cutoff <= Right - Left) { /* 如果序列元素充分多,进入快排 */
Pivot = Median3(A, Left, Right); /* 选基准 */
Low = Left;
High = Right - 1;
while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/
while (A[++Low] < Pivot);
while (A[--High] > Pivot);
if (Low < High) {
Swap(&A[Low], &A[High]);
} else {
break; // while(1)
}
}
Swap(&A[Low], &A[Right - 1]); /* 将基准换到正确的位置 */
Qsort(A, Left, Low - 1); /* 递归解决左边 */
Qsort(A, Low + 1, Right); /* 递归解决右边 */
} else {
InsertionSort(A + Left, Right - Left + 1); /* 元素太少,用简单排序 */
}
}

void QuickSort(ElementType A[], int N) { /* 统一接口 */
Qsort(A, 0, N - 1);
}

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
int key;
PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];

int GetDigit(int X, int D) { /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;

for (i = 1; i <= D; i++) {
d = X % Radix;
X /= Radix;
}
return d;
}

/**
* <p>基数排序</p>
* 每次选择一个基准,如个位、十位、百位
* @param A
* @param N
*/
void LSDRadixSort(ElementType A[], int N) { /* 基数排序 - 次位优先 */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = 0; i < N; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面开始排序 */
for (D = 1; D <= MaxDigit; D++) { /* 对数据的每一位循环处理 */
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶尾 */
tmp->next = NULL;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {
B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* 下面是收集的过程 */
List = NULL;
for (Di = Radix - 1; Di >= 0; Di--) { /* 将每个桶的元素顺序收集入List */
if (B[Di].head) { /* 如果桶不为空 */
/* 整桶插入List表头 */
B[Di].tail->next = List;
List = B[Di].head;
B[Di].head = B[Di].tail = NULL; /* 清空桶 */
}
}
}
/* 将List倒入A[]并释放空间 */
for (i = 0; i < N; i++) {
tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}

/* 基数排序 - 主位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */

#define MaxDigit 4
#define Radix 10

///* 桶元素结点 */
//typedef struct Node *PtrToNode;
//struct Node{
// int key;
// PtrToNode next;
//};

///* 桶头结点 */
//struct HeadNode {
// PtrToNode head, tail;
//};
typedef struct HeadNode Bucket[Radix];

//int GetDigit ( int X, int D )
//{ /* 默认次位D=1, 主位D<=MaxDigit */
// int d, i;
//
// for (i=1; i<=D; i++) {
// d = X%Radix;
// X /= Radix;
// }
// return d;
//}

void MSD(ElementType A[], int L, int R, int D) { /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
int Di, i, j;
Bucket B;
PtrToNode tmp, p, List = NULL;
if (D == 0) return; /* 递归终止条件 */

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = L; i <= R; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶 */
if (B[Di].head == NULL) B[Di].tail = tmp;
tmp->next = B[Di].head;
B[Di].head = tmp;
}
/* 下面是收集的过程 */
i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
for (Di = 0; Di < Radix; Di++) { /* 对于每个桶 */
if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
p = B[Di].head;
while (p) {
tmp = p;
p = p->next;
A[j++] = tmp->key;
free(tmp);
}
/* 递归对该桶数据排序, 位数减1 */
MSD(A, i, j - 1, D - 1);
i = j; /* 为下一个桶对应的A[]左端 */
}
}
}

void MSDRadixSort(ElementType A[], int N) { /* 统一接口 */
MSD(A, 0, N - 1, MaxDigit);
}

//int main() {
// int a[] = {3, 1, 2};
// QuickSort(a, 3);
//}

摊还分析

高级数据结构及其实现

WDF Windows Driver Frameworks Windows 程序驱动程序框架

INF driver setup information 设备安装信息

JSON (JavaScript Object Notation)

阅读全文 »

dp

Density-independent Pixels 像素无关密度

一个基于屏幕物理密度的抽象的单位。

TA 与 屏幕物理密度/像素密度 相关,对应不同的 density

阅读全文 »

使用

By default, to avoid poor UI performance, Room doesn’t allow you to issue queries on the main thread. When Room queries return LiveData, the queries are automatically run asynchronously on a background thread.

为避免糟糕的 UI 性能,Room 不允许你在主线程查询数据库。但当查询返回 LiveData 时,查询将自动异步运行在后台线程。

阅读全文 »

REST (REpresentational State Transfer) 表现层状态转换。

REST 是一种设计风格,便于不同软件在网络上传递信息。

SOAP

SOAP (Simple Object Access Protocol) 简单对象访问协议。

SOAP 是网络交换数据的一种协议规范。

RESTful

REST 是名词,RESTful 是动词。

RESTful API

符合 REST 风格的 API 称为 RESTful API。

要绘制东西,需要 4 个基本组件:存储像素点的 Bitmap、主持绘制的 Canvas、绘图的基本元素(Path,Rect,text,Bitmap等)、描述颜色和样式的 Paint。

阅读全文 »

自定义 View 有两种方法:

继承 View 的子类,如TextView

直接继承 View 类。需要自己绘制 UI 元素。

阅读全文 »

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
// 2020-3-29 19:45:53
// kotlin coroutines
implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.5'
// Glide
implementation 'com.github.bumptech.glide:glide:4.11.0'
annotationProcessor 'com.github.bumptech.glide:compiler:4.11.0'
// OkHttp
implementation 'com.squareup.okhttp3:okhttp:4.4.0'
// ViewPager2
implementation "androidx.viewpager2:viewpager2:1.0.0"
// dagger
// apply plugin: 'kotlin-kapt'
def dagger_version = "2.27"
implementation "com.google.dagger:dagger:$dagger_version"
kapt "com.google.dagger:dagger-compiler:$dagger_version"
// material
implementation 'com.google.android.material:material:1.2.0-alpha05'
// 2020-4-9 14:47:57
// retrofit
implementation 'com.squareup.retrofit2:retrofit:2.8.1'
implementation 'com.squareup.retrofit2:converter-gson:2.8.1'
// Room
// apply plugin: 'kotlin-kapt'
def room_version = "2.2.3"
implementation "androidx.room:room-runtime:$room_version"
kapt "androidx.room:room-compiler:$room_version"
// optional - Kotlin Extensions and Coroutines support for Room
implementation "androidx.room:room-ktx:$room_version"
// Lifecycle
implementation "androidx.lifecycle:lifecycle-extensions:2.2.0"
kapt "androidx.lifecycle:lifecycle-compiler:2.2.0"
implementation "androidx.lifecycle:lifecycle-viewmodel-ktx:2.2.0"
// coroutines
api "org.jetbrains.kotlinx:kotlinx-coroutines-core:1.3.4"
api "org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.4"

Navigation 组件由下面3个关键部分组成:

Navigation Graph XML resource 包含与navigation有关的所有信息,如destination path等。

NavHostFragment Layout XML 添加到layout的widget,显示了Navigation Graph的destination。

NavController Kotlin/Java 对象 追踪在 Navigation Graph 中的位置,协调那些destination。

阅读全文 »

配置(Android)

1
2
// kotlin coroutines
implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.5'

示例:加载网络图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MainActivity : AppCompatActivity() {

override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_main)
val coroutineScope = CoroutineScope(Dispatchers.Main)
coroutineScope.launch(Dispatchers.Main) {
val url = getImageUrl()
Glide.with(this@MainActivity).load(url).into(iv)
}

}

private suspend fun getImageUrl() = withContext(Dispatchers.IO) {
val client = OkHttpClient()
val request = Request.Builder()
.url("http://guolin.tech/api/bing_pic")
.build()
return@withContext client.newCall(request).execute().body?.string()
}
}

withContext()可以切换到指定的线程,然后在闭包内的逻辑结束后,再切换到原来的线程继续执行。

Dispatchers

2020-03-21 22:09:50

CSS

CSS 用于指示 HTML 在浏览器中的显示样式。

CSS 组成

CSS 由选择符(选择器)与声明组成,声明由属性和值组成。

1
2
3
p {
color: blue;
}
阅读全文 »

HTML

sample

1
2
3
4
5
6
7
8
9
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>制作我的第一个网页</title>
</head>
<body>
<h1>Hello HTML</h1>
</body>
</html>
阅读全文 »

开始

对一个对象实例调用多个方法(使用 with)

阅读全文 »

简介

HTTP (Hypertext Transfer Protocol 超文本传输协议)是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP 协议定义了客户端如何从服务器请求 Web 页面,以及服务器如何把 Web 页面返回给客户端。HTTP 是万维网数据通信的基础。

阅读全文 »

Service是一种可以在后台执行长时间运行操作而不提供界面的应用组件。

阅读全文 »

Android 构建时会编译源代码和应用资源,然后打包为APK文件。Android Studio 使用 Gradle 来自动执行和管理构建流程。Android Plugin for Gradle 与 Gradle 搭配使用,专门为 Android 应用的构建提供支持。

阅读全文 »

启用 Data Binding

Data Binding 库与 Android Gradle 插件捆绑在一起,所以不需要声明依赖,但需要启用。

阅读全文 »

概述

数字系统

可以用不同数字反映的物理量称为数字量。

表示数字量的信号称为数字信号。

处理数字信号的电子电路称为数字电路(数字逻辑电路、逻辑电路),其功能通过逻辑运算和逻辑判断完成。

阅读全文 »

写在前面

make这一阶段花费时间和机器配置有关,可能长达几小时,建议选择好时间。同时需要足够的磁盘空间,22G以上。

环境:Ubuntu 18.04.1 阿里云服务器

阅读全文 »

前言

注解在Java SE5中引入。注解好处多多,TA可以使我们的代码变得简洁,减少样板代码,还能存储有关程序的额外信息。程序员还可以自定义注解

阅读全文 »

前言

这是打算认真写博客后的第一篇,今天来研究一下Java的反射机制。

反射简介

反射机制可以让人们在运行时获得类的信息。

Class类和java.lang.reflect类库(包含Constructor Method Field Modifier Array类)为反射提供了支持。

阅读全文 »