数据结构课程复习

考查目标：

1. 理解数椐结构的基本概念、掌握数椐的逻辑结构、存储结构及其差异，以及各种基本操作的实现。
2. 掌握基本的数据处理原理和方法，在此基础上能够对算法进行设计与分析。
3. 能够选择合适的数椐结构和方法进行问题求解。

以西北工业大学801计算机专业基础为考纲

零、绪论

0.1 基本概念

0.1.1 逻辑结构分类

分类	线性存储结构	非线性存储结构
特点	数据元素有序集合，“一对一”	“一对多”
举例	线性表	图形、网状、树形结构

有序表和无序表是逻辑上有序无序，是逻辑结构。栈、队列也是逻辑结构。

0.1.2 存储结构分类

存储结构也称物理结构：是数据逻辑结构在计算机中的表示（映像）。包括数据元素的表示和关系的表示。

数据元素之间的表示方法分为顺序映像和非顺序映像？

常用的存储结构：顺序存储、链式存储、索引存储、散列存储（散列是一种算法）。（存储结构的是：环形队列、散列表、单链表、顺序表。）

顺序表、哈希表、单链表都是存储结构。

线索树是链式存储结构上的基础上对树进行线索；

双向链表是线性表以链式存储结构存储；

循环队列是建立在顺序存储结构上的；

栈是逻辑结构，顺序栈和链栈是存储结构。

栈和队列是特殊的线性表，线性表的存储结构为：顺序表和链表。对应的栈为顺序栈和链栈；队为顺序队和链队。

0.2 算法及其分析

算法的时间复杂度：

问题规模：输入量的多少

算法时间分析的就是求出算法所有原子操作的执行次数（频度），它是问题规模n的函数，用T(n)表示。

原子操作的个数m，算法执行时间$t=m\times T(n)$.

for(int i=0; i<n; i++){     // 频度n+1，执行次数n
  for(int j=0; j<n; j++){   // 频度n(n+1)，执行次数n^2
    // 语句s                 // 频度1*n^1，执行次数n^2
  }
}

$$T(n)=n+1+n*(n+1)+n^2=2n^2+2n+1$$，用数量级表示，$$T(n)=o(n^2)$$

求和定理：算法中while循环的if条件中包含的语句可以不考虑，因为它的执行次数不超过循环条件语句的频度。

求积定理

0.2.1 题型总结

• 普通循环

void fun(int n){    // 设while循环执行次数为m，
  int i=0, s=0;     // i从1到m，s=1+2+...+m=m(m+1)/2
  while(s<n){       // 所以循环结束时有 s=m(m+1)>=n
    i++; s=s+i;     // 总有常数k，使 m(m+1)/2+k=n
  }
}

得$m=\frac{-1+\sqrt{8n-8k+1}}{2},\quad T(n)=m=o(\sqrt{n})$

void fun(int n){      // 同理，执行m次后，i=2^m
  int i=1;            // 循环结束时有： i>n  得 m>log_2{n}
  while(i<=n) i=i*2;  // 总有常数k，使m=log_2{n}+k
}                     // T(n)=m=O(log_2{n})

void fun(int n){      // 利用到上面的求和定理，p=p*f不考虑
  int p=1, d=n, f=n;  // 因为他的执行次数不超过d=d/2语句的频度
  while(d>0){         // 同理，执行m次后，d=n/2^m>=0
    if(d%2==1) p=p*f; // 所以结束时，只能是d=0，计算机中当n=1时，才有d=0
    f=f*f;            // 则n/2^m>=1， m<=log_2{n}
    d=d/2;            // T(n)=m=O(log_2{n})
  }
}

void fun(int n){            // i=1时，j从n到2，执行n-2+1=n-1次
  int i, j, x=0;            // i=2时，j从n到3，执行n-2次
  for(i=1; i<n; i++)        // ...
    for(j=n; j>=i+1; j--)   // i=n时，j从n到n，执行1次
      x++;                  // T(n)=n-1+n-2+...+1=(n-1)(n-1+1)/2=O(n^2)
}

• 算法的平均时间复杂度，最好时间复杂度，最坏时间复杂度

/*求前i(1<=i<=n)个元素的最大值*/
int fun(int a[], int n, int i){    // 1的取值可以是1~n，有n种情况，等概率1/n
  int j, max=a[0];                 // 每种情况都要比(i-1)-1+1=i-1次
  for(j=1; j<=i-1; j++)            // 则Tn=见下
    if(a[j]>max) max=a[j];         // 所以平均时间复杂度O(n)
  return max;                      // 最好情况i=1，O(1)；最坏情况i=n，O(n)
}

$$T_n=\sum_{i=1}^n \frac{1}{n}(i-1)=\frac{n-1}{2}=O(n)$$

/*递归算法时间复杂度分析*/
void hanoi(int n, char x, char y, char z){   // 设函数hanoi(n,...)的执行时间为T(n)
  if(n==1)                                   // 则hanoi(n-1,...)的执行时间为T(n-1)
    printf("move %c to %c\n", x, z);         // 当n=1有T(1)=1
  else{                                      // 根据代码：当n>1时，T(n)=2T(n-1)+1
    hanoi(n-1, x, z, y);                     // 所以，有
    printf("move %c to %c\n", x, z);         // T(n)=2T(n-1)+1=2(2T(n-2)+1)+1
    hanoi(n-1, y, x, z);                     //     =2^2T(n-2)+2+1
  }                                          //     =...
}                                            //     =2^2+1=O(2^2)

• 值得记的递归算法

/*假设非空二叉树bt采用二叉链存储，其中所有节点数据域为正数，设计一个递归算法求其中的最大值。*/
/*解：设二叉链表bt中最大值为f(bt)，推导得*/
/*[递归模型]：*/
/*f(bt)=0                                             若bt为空*/
/*f(bt)=bt->data                                 若bt是叶子节点*/
/*f(bt)=MAX(bt->data, f(bt->lchild), f(bt->rchild))   其他情况*/
// 递归算法如下：
int f(BTNode *bt){
  int m, n; // m存放左子树最大值，n存放右子树最大值
  if(bt==NULL)
    return 0;
  if(bt->lchild==NULL && bt->rchild)
    return bt->data;
  else{
    m=f(bt->lchild); // 求左子树中最大值
    n=f(bt->rchild); // 求右子树中最大值
    if(m<=n)
      m=n; // 左、右子树中的最大值放在m中
    if(m>bt->data) // 由于是个3值比较，先比较子树两个值，再与父父节点比较
      return m; // 返回最大值
    else
      return bt->data;
  } // end else
} // end function

一、线性表

1.1 线性表的定义和基本操作

线性表（Linear List）描述：线性表是n个类型相同数据元素的有限序列，对n>0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每个元素只有一个直接前驱和一个直接后继，元素之间具有一对一的关系。

1.2线性表的实现

1.2.1 顺序存储结构

• 顺序表的定义

顺序表是一种顺序存储结构，是线性表在内存中的一种直接映射方式。

所谓随机存储特性指通过首地址和元素序号可以在O(1)时间内找到指定元素。

顺序表的插入删除操作时间复杂度为O(n)。通过计算平均移动次数（平均时间复杂度）

$$存储密度=\frac{节点数据本身占用的存储量}{节点结构占用的存储量}$$

顺序表的存储密度为1，而链表小于1。

• 有序表的定义

元素有序排列，逻辑结构，顺序链式进行存储，不能随意指定插入元素的位置。

1.2.2 链式存储结构

• 单链表的定义

  单链表中用任意一组存储单元存放线性表中的元素，每个节点通过一个指针指向后继节点。

  头结点和首节点的区别，首节点是有值的。头插法、尾插法建单链表的时间复杂度O(n)

• 双链表的定义（双向链表）

  每个节点通过两个指针分别指向前驱和后继节点。

• 循环链表的定义

  循环单链表是将原单链表中尾节点的next域由NULL改为指向头节点。

  循环双链表是将原双链表中尾结点的next域由NULL改为指向头节点，再将头节点的prior域改为指向为节点。

  // 带头结点的循环链表L中，某节点*p为尾结点的条件是
  p->next==L;

1.3 线性表的应用

二、栈、队列和数组

2.1 栈和队列的基本概念

都是插入和删除操作受限的线性表。

2.1.1 栈的定义

栈顶进行插入和删除，另一端叫栈底。（先进后出，后进先出）

2.1.2 队列的定义

队尾插入，对头删除。（先进先出，后进后出）

2.2 栈和队列的顺序存储结构

2.2.1 顺序栈

• 顺序栈s的4要素

  // 栈空条件
  s.top==-1;
  // 栈满条件
  s.top==MaxSize-1;
  // 元素e进栈
  s.top++; s.data[s.top]=e;
  // 元素出栈
  e=s.data[s.top]; s.top--;

2.2.2 共享栈

两个栈共享一个数组空间，两端固定，即两栈栈底固定。下标0的一段作为栈1的栈底，其栈顶指针top1；将下标MaxSize-1的一端作为栈2的栈底，其栈顶指针为top2。

• 栈1的4要素

  // 栈空条件
  s.top1==-1;
  // 栈满条件
  s.top1==s.top2-1;
  // 元素e进栈
  s.top1++; s.data[s.top1]=e;
  // 元素出栈
  e=s.data[s.top1]; s.top1--;

• 栈2的4要素

  // 栈空条件
  s.top2==MaxSize;
  // 栈满条件
  s.top2==s.top1+1;
  // 元素e进栈
  s.top2--; s.data[s.top2]=e;
  // 元素出栈
  e=s.data[s.top2]; s.top2++;

2.2.3 顺序队

数组存放队中元素，用front和rear两个变量分别指示队头和队尾，front指向队列中队首元素的前一个位置，rear指向队尾元素的位置。（也就是front指向的空间没有值，像这样的队列最多只能进队MaxSize-1个元素）

• “假溢出”现象

  当队列中实际元素个数远远小于数组大小时，也可能由于队尾指针已超过数组上界而不能做进队操作。

  为此，将数组通过逻辑方法改为首尾相连，这样的队列称为环形队列（或循环队列）。

• 环形队列q的4要素

  // 队空条件
  q.front==q.rear;    // rear指向的空间也可能没有值
  // 队满条件
  (q.rear+1)%MaxSize==q.front;
  // 元素e进队
  q.rear=(q.rear+1)%MaxSize;  q.data[q.rear]=e;
  // 元素出队
  q.front=(q.front+1)%MaxSize;  e=q.data[q.front];

2.3 栈和队列的链式存储结构

2.3.1 链栈

可以采用带头结点的单链表表示，也可以采用不带头结点的单链表表示。

• 链栈s的4要素

  // 栈空条件
  s->==NULL;
  // 栈满条件
  不存在;
  // 元素e进栈
  建立值为e的节点*p，采用头插法插入到链栈中;
  // 元素出栈
  取出首节点的data值并删除之;

2.3.2 链队

通常链队用不带头结点的单链表表示？其中有两种类型的节点，一是存放队列中数据元素的节点，另一种是存放对头、队尾指针的链队节点，一个链队只有一个链队节点。

• 链队q的4要素

  // 队空条件
  q->front==NULL&&q->rear==NULL;
  // 队满条件
  不存在;
  // 元素e进队
  建立一个data域为e的数据节点*s，将*s插入到队尾并让q->rear指向它;
  // 元素出队
  取出队首节点的data值，将其删除并让q->front指向下一个节点;

2.3.3 双端队列

两端（前端和后端）都可以入队和出队。其元素的逻辑结构仍是线性结构。

2.4 栈和队列的应用

2.4.1 栈的应用

• 将算术表达式exp转换为后缀表达式postexp

法一：算法基本思想

采用运算符栈是为了比较运算符的优先级，所有的运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先退栈的运算符先计算，同优先级的运算符在栈中计算）

法二：手工加括号

过程：先根据中缀表达式的求值次序加上括号，将右括号用相应的运算符替换，再除掉所有左括号。

例如：中缀表达式$5+2*(1+6)-8/2$，加括号变为：$((5+(2*(1+6)))-(8/2))$

用这种对应关系$((5\underbrace{+(2{\underbrace{*(1\underbrace{+6)})}})}\underbrace{-(8\underbrace{/2)})}$，往回找，就近原则。

将右括号用对应的运算符替换，变为：$((\ 5\ (\ 2\ (\ 1\ 6\ +\ *\ +\ (\ 8\ 2\ /\ -$

最后除掉所有左括号得到后缀表达式为$5\ 2\ 1\ 6\ +\ *\ +\ 8\ 2\ /\ -$

• 对后缀表达式求值

2.5 数组的基本概念

数组是由相同类型的数据元素构成的一个有限序列，对于$m(m\geq1)$维数组，每个元素受m个线性关系的约束，所以数组是线性表的推广。

数组具有随机存储的特性（存储连续，随机访问，通过下标；链表存储连续，访问连续？）

2.5.1 特殊矩阵的压缩存储

n阶对称矩阵$A[1...n]A[1...n]$存放在一维数组$B[1...\frac{n(n+1)}{2}]$中，即元素$a_{ij}$存放在$b_k$中，即只存放主对角线元素和下三角区的元素$(i \ge j)$。

就是求出i，j和k的关系。求顺序号，即它前面有几个元素。

$$\begin{bmatrix} {a_{11}}&{a_{12}}&{a_{13}}&{\cdots}&{a_{1n}}\\ {a_{21}}&{a_{22}}&{a_{23}}&{\cdots}&{a_{2n}}\\{a_{31}}&{a_{32}}&{a_{33}}&{\cdots}&{a_{2n}}\\ {\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\\{\vdots}&{\vdots}&{a_{ij}}&{\ddots}&{\vdots}\\{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{n1}}&{a_{n2}}&{a_{n3}}&{\cdots}&{a_{nn}}\\ \end{bmatrix}$$

求$a_{ij}$前面有$(1+2+\cdots+i-1)+j-1=\frac{(i-1)(i-1+1)}{2}+j-1=\frac{i(i-1)}{2}+j-1$个元素，得：

$$k= \begin{cases} \cfrac{i(i-1)}{2}+j, &当i\ge j(下三角区和主对角线元素)\\ \cfrac{j(j-1)}{2}+i, &当i<j(上三角区元素a_{ij}=a_{ji}) \end{cases}$$

2.5.2 三角矩阵

矩阵中上三角区的所有元素均为同一变量c，只需存放下三角区，主对角线上的元素和常量c。

2.5.3 对角矩阵

$$k=2i+j-2$$

2.5.4 稀疏矩阵

定义：非零元素远小于元素总数的二维数组。压缩方法是只存非零元素。

常用的存储结构有三元组（行、列号和权值）表示和十字链表表示。

三、树与二叉树

3.1 树的概念

树是由$\mathtt{n}(\mathtt {n}\geq0)$个节点组成的有限集合。其中，如果$\mathtt {n}=0$，它是一棵空树；如果$\mathtt {n}>0$，这$\mathtt {n}$个节点作为树的根节点，其余节点可分为$m(m\geq0)$个互不相交的有限集，其中每一棵自己本身又是一棵符合本定义的树，称为根节点的子树。

• 基本术语

  度：树中各节点的度的最大值；

  分支节点：度不为0的节点称为非终端结点，又叫分支节点；

  叶子节点：度为0的节点称为终端结点，或叶子节点；

  孩子节点、双亲结点和兄弟节点

  节点的层次：根节点为第一层；

  树的高度（深度）：节点的最大层次；

  路径：由经过的节点序列构成；

  路径长度：经过的边的数目（树中分支是有向的，从上向下，兄弟节点间无路径）；

  森林：$n(n\ge 0)$个互不相交的树的集合。

• 树的性质

  性质1：树中节点数为n，度之和 等于 分支数，分支数=n-1

  性质2：度为m的树中第i层上至多有$m^{i-1}$个结点$i\ge 1$

  性质3：高度为h的m次树至多有$\frac{m^{h-1}}{m-1}$个结点（等比数列前n项和）

  性质4：具有n个结点的m次树的最小高度为$\lceil log_m{[n(m-1)+1]} \rceil$

• 树的存储结构

  • 双亲存储结构

    连续空间存储树的所有结点

    

  • 孩子链存储结构

    按树的度设计节点的孩子节点指针域个数（m叉树的一个节点的指针域m个，加数据域共m+1域）

    

  • 孩子兄弟链存储结构

    3个域：数据元素域、第一个孩子域、下一个兄弟节点指针域。

3.2 二叉树

3.2.1 二叉树的定义及其主要特征

二叉树是$n(n\ge 0)$个结点的有限集合，该集合或者为空集$(n=0)$，或者由一个根节点或两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树不同于度为2的树，度为2的树至少有3个结点，不区分子树的次序。

完全二叉树的特点：

• 如果有度为1的节点，只能有一个，且该节点只有左孩子而无右孩子
• 当节点总数n为奇数时，$n_1=0$；当节点总数n为偶数时，$n_1=1$

3.2.2 二叉树的性质

• 性质1：非空二叉树上叶子节点数等于双分支节点数加1，即$n_0=n_1+1$

  （度之和 等于 节点数-1）$\Rightarrow$叶子节点数 等于 度为2的节点数+1

• 性质2：非空二叉树上第i层上至多有$2^{i-1}$个结点。$(i\ge 1)$

• 性质3：高度为h的二叉树至多有$2^{h-1}(\frac{2^{i-1}}{2-1})$个结点。$(h\ge 1)$

• 性质4：若二叉树采用顺序存储结构表示，则编号为 i 和 j 的两个节点处于同一层的条件是$\lfloor log_2(i+1) \rfloor=\lfloor log_2(j+1) \rfloor$

3.2.3 二叉树的顺序存储结构

用一组地址连续的存储单元存放（没有结点的地方用’#’字符填补）

3.2.4 二叉树的链式存储结构

3.2.5 二叉树的遍历

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根
• 层次遍历
• 基于递归的二叉树算法设计方法
• 基于非递归的二叉树算法设计方法

3.2.6 二叉树的构造

• 由先序序列和中序序列构造二叉树
• 由后序序列和中序序列构造二叉树
• 由层次序列和中序序列构造二叉树

3.2.7 线索二叉树的基本概念和构造

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该节点的前驱节点和后续节点的指针，这些指针称为线索。加上线索的二叉树称为线索二叉树。提高遍历过程的效率。

3.3 二叉排序树（Binary Search Tree, BST）

二叉排序树或是一颗空树，或者是满足如下性质的二叉树：

• 若其左子树非空，则左子树上所有的记录的值均小于根记录的值；
• 若其右子树非空，则右子树上所有的记录的值均大于根记录的值；
• 左、右子树本身又各是一颗BST。

BST按中序遍历该树所得到的中序序列是一个递增有序序列。

3.4 平衡二叉树（AVL）

平衡二叉树或是一颗空树，或者是具有下列性质的二叉排序树：

• 其左子树和右子树都是AVL；
• 且左、右子树高度之差的绝对值不超过1。

平衡因子定义为节点左子树的高度减去它的右子树的高度$(-1, 0, 1)$。

3.4.1 平衡二叉树中插入一个新节点的方法

• LL型调整
• RR型调整
• LR型调整
• RL型调整

3.4.2 平衡二叉树中删除一个节点的方法

3.4.3 平衡二叉树查找节点的过程

含有n个节点的平衡二叉树的平均查找长度为$O(log_2n)$。

四、树、森林

4.1 树的存储结构

• 双亲存储结构

双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。（求某节点双亲结点$o(1)$，求某节点孩子$O(n)$）

注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。

• 孩子链式存储结构

按树的度设计节点指针域个数。就是一个父节点链上其所有孩子节点。

• 孩子兄弟链存储结构

3个域：数据元素域，第一个孩子域，下一个兄弟节点指针域。

4.2 森林与二叉树的转换

树的先根序列对应二叉树的先序序列；树的后根序列对应二叉树的中序序列。

4.2.1 森林、树转换为二叉树

4.2.2 二叉树还原为森林、树

4.3 树与森林的遍历

4.4 树的应用

4.5 等价类问题

4.6 哈夫曼树和哈夫曼编码

带权路径长度：从根节点到该节点之间的路径长度与该节点权值的乘积。

树的带权路径长度：树中所有叶子节点的带权路径长度之和。记为：

$$WPL=\sum_{i=0}^NW_iL_i$$

其中，n表示叶子节点的数目，$W_i$表示叶子节点的权值，$L_i$表示根到该叶子节点间的路径长度。

哈夫曼树：在n个带权叶子节点构成的所有二叉树中，带权路径长度WPL最小的二叉树。

• 哈夫曼树的构造算法

哈夫曼编码中没有单分支节点，即$n_1=0$

• 哈夫曼编码

在哈夫曼树的基础上构造哈夫曼编码的过程如下：

规定哈夫曼树中所有左分支为0，右分支为1；

从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的哈夫曼编码。

得到相应字符传输的编码数据：

A    B    C    D    E    F
01   1001 101  00   11   1000

只对叶子编码，不存在两个编码相同的叶子，不存在一个编码是另一个编码的前缀。

五、图

5.1 图的概念

图G分别由两个集合V和E组成，记为$G=(V,E)$，其中V是顶点的有限非空集合，E是V中序偶的有限集，这些序偶称为边。

    1               表示为： G=(V,E)
 /  |  \ 
2 - 3   0                   V={0,1,2,3,4}
 \     /
    4                       E={(0,1),(0,4),(1,2),(1,3),(2,3),(2,4)}

• 无向图：在图G中，如果表示边的序偶是无序的（用圆括号表示），则G为无向图；

• 有向图：在图G中，如果表示边的序偶是有序的（用尖括号表示），则G为有向图；

• 完全图：若图中的每两个顶点之间都存在着一条边，称该图为完全图；

  具有n个顶点的完全有向图有$n(n-1)$条边，完全无向图有$\frac{n(n-1)}{2}$条边；

• 端点：在一个无向图中，若存在一条边$(v_i,v_j)$，则称$v_i$和$v_j$为此边的两个端点，并称他们互为邻接点；

  在一个有向图中，若存在一条边$<v_i,v_j>$，则称$v_i$和$v_j$为此边的两个端点，也称他们互为邻接点，$v_i$为起点，$v_j$为终点；

• 顶点的度、入度和出度

• 子图：设有两个图$G=(V,E)$和$G^{'}=(V^{'},E^{'})$，若$V^{'}$是$V$的子集，即$V^{'}\subseteq V$，且$E^{'}$是$E$的子集，则称$G^{'}$是$G$的子图；首先$G^{'}$是个图才行；

• 路径：在一个图$G=(V,E)$中，从$v_i$到$v_j$的一条路径是一个顶点序列$(v_i,v_{i1},...v_{im},v_j)$，若此图G是无向图，则边$(v_i,v_{i1}),(v_{i1},v_{i2}),...,(v_{im},v_j)$属于$E(G)$；若此图是有向图，则$<v_i,v_{i1}>,<v_{i1},v_{i2}>,...,<v_{im},v_j>$属于$E(G)$；

• 路径长度：指一条路径上经过的边的数目。若一条路径上除开始和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径；

• 回路（环）：若一条路径上的开始点与结束点为同一顶点，则称此路径为回路或环；开始点与结束点相同的简单路径被称为简单回路或简单环；回路不能说是简单路径；

• 连通：在无向图G中，若从$v_i$到$v_j$有路径，则称$v_i$和$v_j$是连通的；

• 连通图：若图G中任意两个顶点都连通，则称G为连通图，否则，称为非连通图；

• 连通分量：无向图G中的极大连通子图称为G的连通分量；显然，任何连通图的连通分量只有一个，即本身；而非连通图有多个连通分量；

• 强连通分量：若有向图G中的极大强连通子图称为G的强连通分量；显然，非强连通分量有多个强连通分量；

• 稠密图：当一个图G接近完全图时，则称为稠密图；

• 稀疏图：当一个图含有较少的边数（即当$e<<n(n-1)$）时，称为稀疏图；

• 权：图中每一条边都可以附有一个对应的正数，与边相关的正数称为权；

• 网：边上带有权的图称为带权图，也称作网。

5.2 图的存储及基本操作

5.2.1 邻接矩阵法（图的顺序存储结构）

• $A[i][j]=1$表示顶点i邻接顶点j，$A[i][j]=0$表示顶点i与顶点j不邻接。带权图中，通常约定矩阵$A[i][i]=0$；
• 无向图的邻接矩阵是对称矩阵；
• 对于有向图矩阵中的“1”的个数为图的边数，第i行元素之和为i的出度，第j列元素之和为j的入度；
• 邻接矩阵只能表示顶点之间的相邻关系，若要存储图中的顶点信息必须用另一个一维数组存放。若是带权图，图中顶点i与顶点j邻接且权值为$w_{ij}$，则$A[i][j]=w_{ij}$，不邻接，则$A[i][j]=\infty$，通常约定$A[i][i]=0$；

5.2.2 邻接表法（图的链式存储）

• 所有顶点表节点构成一个数组，顶点表节点存放顶点信息和指向第一个邻接点的指针；边表节点；
• 对于有向图边表中的节点数就等于图中边数，每个单链表的节点数就是相应顶点的出度；
• 图的邻接表不唯一；对于n各顶点和e条边的无向图，其邻接表有n个顶点表节点和2e个边表节点。显然，在总边数小于$\frac{n(n-1)}{2}$的情况下，邻接表比邻接矩阵要节省空间。（即对于完全无向图，邻接表与邻接矩阵花费空间相同）。

5.3 图的遍历

5.3.1 深度优先搜索（DFS）

递归，可用于求简单路径。

5.3.2 广度优先搜索（BFS）

类似于树的层次遍历，借助队列。

由于每个顶点表节点和边表节点都要扫描一次，所以：

• 采用邻接表存储时，BFS和DFS的时间复杂度都是$O(n+e)$，空间复杂度都是$O(n)$；
• 采用邻接矩阵存储时，BFS和DFS的时间复杂度和空间复杂度都是$O(n^2)$；

5.3.3 非连通图的遍历

对于无向图，调用$DFS(G, i)$或$BFS(G, i)$几次，说明该图中有几个连通分量。

总结：

算法	邻接表时	空间复杂度	邻接矩阵时
DFS	$O(n+e)$	$O(n)$	$O(n^2)$
BFS	$O(n+e)$	$O(n)$	$O(n^2)$

5.4 图的基本应用及其复杂度分析

5.4.1 最小（代价生成树）

生成树：在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图$G^{'}$，即：$V(G^{'})=V(G)$和$E(G^{'})\subseteq E(G)$ ，若边集$E(G^{'})$中的边将图G中的所有顶点连通，又不形成回路，则称子图$G^{'}$是原图G的一棵生成树。

具有权值之和最小的生成树称为图的最小生成树。

图的最小生成树不唯一，当存在相同权值的边时，其最小生成树也可能不唯一。一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。之所以称为极小是因为此时如果删除一条边，就无法构成生成树。

• 普里姆（Prim）算法

  Prim算法是一种增量（构造型）算法，一步一步地选择最小边。

  由于Prim算法中需要频繁地取一条条边的权值，所以采用邻接矩阵更合适。

  Prim算法中有两重for循环，所以时间复杂度$O(n^2)$，n为图的顶点个数。

  时间复杂度与边数e无关，适用于稠密图。

• 克鲁斯卡尔（Kruskal）算法

  算法时间复杂度$O(e*log_2e)$，适合稀疏图。是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

• 总结

最小生成树算法	时间复杂度	适用于
普里姆算法	$O(n^2)$	稠密图
克鲁斯卡尔算法	$O(e*log_2e)$	稀疏图

5.4.2 最短路径

对于带权有向图G，最短路径是指从一个顶点到达另一个顶点所经过的边上的权值之和最小的路径，而不是边数最少的路径。

• 从一个顶点到其余各顶点的最短路径

  采用迪克斯特拉（Dijkstra）算法求解，算法时间复杂度$O(n^2)$

• 每对顶点之间的最短路径

  采用弗洛伊德（Floyd）算法，时间复杂度$O(n^3)$

• 总结

算法	功能	时间复杂度	适用于
迪克斯特拉算法	从源点到其余各顶点最短路径	$O(n^2)$	带权图最短路径；任两顶点
迪克斯特拉算法	每对顶点间最短路径	$O(n^3)$
弗洛伊德算法	每对顶点间最短路径	$O(n^3)$

5.4.3 拓扑排序

• AOV网的定义（Activity On Vertex Network）

  利用顶点表示活动，边表示活动间的先后关系的有向图称为顶点活动图，简称AOV网。在网中，若从$v_i$到$v_j$有一条有向路径，则$v_i$是$v_j$的前趋，$v_j$是$v_i$的后继。若$<v_i,v_j>$是网中一条弧，则$v_i$是$v_j$的直接前趋，$v_j$是$v_i$的直接后继。AOV网中的弧表示活动之间的优先关系。

• 拓扑排序

  设$G=(V,E)$是一个具有n个顶点的有向图，V中的顶点序列$v_1,v_2,...,v_n$称为一个拓扑序列。

  • 在一个有向图中找一个拓扑序列的过程称为拓扑排序。
  • AOV网中不应出现有向换（即无以自己为先决条件的序列）

  给出下列课程间先修关系的有向图：

• 若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图含有顶点数目大于1的强连通分量（即有回路，有向环）。所以判定一个有向图是否存在环（回路）可以用拓扑排序方法。

5.4.4 关键路径

• AOE网的定义（Activity On Edge Network）

  • 在带权有向图中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则此带权有向图称为用边表示活动的网，简称AOE网。
  • 用AOE网表示一项工程计划时，顶点所表示的事件实际上就是该顶点所有进入边所表示的活动均已完成，而该顶点的出发边所表示的活动均可开始的一种状态。
  • AOE网中至少一个源点，其入度为0，同时应有一个汇点，其出度为0；网中不存在回路，否则整个工程无法结束。

• 求关键路径的过程

  在AOE网中，完成工程的最短时间是从开始点到完成点的最长路径长度，路径长度最长的路径叫做关键路径。

  • 事件$v_k$的最早发生时间$ve(k)$

    指从开始顶点到顶点k的最长路径长度；事件的最早发生时间决定了顶点k的所有直接后继活动能够开始的最早时间。

  • 事件$v_k$的最迟发生时间$vl(k)$

    指在不推迟整个工程完成的前提下，该事件必须最迟发生时间；n为结束顶点，$vl(k)$为$ve(n)$减去顶点k到n的最长路径长度。

  • 活动$a_i$的最早开始时间$e(i)$

    指该活动的起点所表示的事件最早发生时间；$e(i)=ve(i)$

  • 活动$a_i$的最迟开始时间$l(i)$

    指该活动的终点所表示的事件最迟发生时间与该活动所需时间之差，$l(i)=vl(k)-a_i$

  • 一个活动$a_i$的最迟发生时间$l(i)$和其最早开始时间$e(i)$的差额$d(i)=l(i)-e(i)$

    指该活动完成的时间余量；这是在不增加完成整个工程所需的总时间的情况下，活动$a_i$可以拖延的时间。

    当活动的时间余量为零时，说明该活动必须如期完成，否则就会拖延完成整个工程的进度，所以和$l(i)-e(i)=0$，即$l(i)=e(i)$的活动$a_i$是关键活动。

• 可以通过加快（或缩短）关键活动来实现缩短整个工期。但并不是加快任一关键活动都可，只有加快那些在所有关键路径上的关键活动；另外，也不能随意缩短，缩短到一定程度，关键活动可能就不关键了。

• 由关键获得构成的路径便是关键路径，关键路径不唯一。

六、查找

6.1 查找的基本概念

定义：给定一个值k，在含有n个记录的表中找出关键字等于k的记录。

静态查找表和动态查找表：若在查找的同时还对表做修改运算（如插入和删除），则相应的表称为动态查找表，否则称之为静态查找表。

评价查找长度（ASL，Average Search Length），也叫平均比较次数。

ASL可分为成功查找情况下和不成功查找情况下ASL两种。

线性表的查找方法主要有：顺序查找、折半查找和分块查找。

6.2 顺序查找法

成功时：$ASL=\sum_{i=0}^np_ic_i=\frac{1}{n}\sum_{i=1}^n=\frac{n+1}{2}$，n是查找表中记录的个数，$p_i$是查找dii个记录的概率，$p_i=\frac{1}{n}$，$c_i$是找到第i个记录所进行的比较次数。

不成功时：$ASL=n$；

时间复杂度$O(n)$，适用于顺序、链式存储。

6.3 折半查找法（二分查找）

要求线性表是有序表。折半查找过程可用二叉树来描述，判定树或比较树。

• 折半查找判定树的形态只与表元素个数n相关。
• 等概率假设下，折半查找成功时，$ASL\approx log_2(n+1)-1$。
• 在最坏情况下查找成功和不成功的比较次数均不超过判定树的高度，即$\lceil log_2(n+1)\rceil$（仅适用于顺序存储）
• 采用折半查找时，查找成功时最多关键字比较次数和不成功时最多关键字比较次数为$\lceil log_2(n+1)\rceil$。

• 例，给定11个数据元素的有序表（2,3,10,15,20,25,28,29,30,35,40），采用折半查找

  • 若查找给定值为20的元素，将依次与25,10,15,20比较，共4次；

  • 若查找给定值为26的元素，依次与25,30,28比较，共3次；

  • 在查找成功时会找到图中某个内部结点，则成功时的评价查找长度：$ASL_{成功}=\frac{1*1+2*2+4*3+4*4}{11}=3$；

    11个元素对应11个内部结点。

  • 在查找不成功时，会找到图中某个外部结点，则不成功的评价查找长度：$ASL_{不成功}=\frac{4*3+8*4}{12}=3.67$。

• 理解难点
  • 对于成功ASL，有11个结点，比如第1层，1个结点比较1次，其查找长度为$1*1$；第2层，2个结点，每个结点查找成功比较2次，且其查找长度之和为$1*2+1*2=2*2$；因此，平均查找长度的意思即把每个结点的查找长度算出来求和，再除以结点数，即得公式；
  • 第4层的外部结点，比如0~1，这种情况（共12种情况），和2比完，比了3次就知道序列中没有这种情况，所以第4层外部结点的查找不成功长度比层数小1，即得公式。

6.4 B-树

6.4.1 m阶B-树的定义

B-树又称多路平衡查找树

B-树中所有结点的孩子节点数目的最大值称为B-树的阶，通常用m表示，从查找效率考虑，要求$m\geq3$。一棵m阶B-树或是一棵空树，或是满足下列要求的m次树：

• 所有的叶子结点在同一层，并且不带信息；
• 树中每个结点至多有m课子树（即至多含有m-1个关键字）；
• 若根结点不是终端结点，则根结点至少有两棵子树；
• 除根结点外，其他非叶子结点至少有$\lceil\frac{m}{2}\rceil$棵子树（即至少含有$\lceil\frac{m}{2}\rceil-1$关键字）；
• 每个非叶子结点的结构（下图）。其中，n为该结点中的关键字个数。除根结点外，其他所有非叶子结点的关键字个数n满足：$\lceil \frac{m}{2}\rceil-1 \leq n\leq m-1$；

有$k_i(1\leq i\leq n)$为该结点的关键字且满足$k_i<k_{i+1}$；

有$p_i(0\leq i\leq n)$为该结点的孩子结点指针且满足：

• $p_0$所指结点上的关键字小于$k_i$；
• $p_i$所指结点上的关键字大于等于$k_i$且小于$k_{i+1}(1\leq i\leq n-1)$；
• $p_n$所指结点上的关键字大于等于$k_n$。

B-树是所有结点的平衡因子均等于0的多路查找树。

如下一图是一个3阶B树：

• 在m阶B-树中，叶子结点可看成是外部结点或查找失败的结点（类似于折半查找判定树的外部结点），需要计入树的高度。
• 除根结点外，非叶子结点的孩子结点个数：$\lceil \frac{m}{2}\rceil \sim m$，关键字个数：$\lceil \frac m2\rceil \sim m-1$，即孩子结点数比关键字个数多1。

6.4.2 B-树的查找

在B树中查找给定关键字的方法类似于二叉排序树上的查找，不同之处在于每个记录上确定向下查找的路径不一定是二路的，而是多路的。

在每个结点内查找关键字既可以用顺序查找，也可以用折半查找。

在一棵B-树上顺序查找关键字为k的方法为：将k与根结点中的$k_i$进行比较：

• 若$k=k_i$，则查找成功；
• 若$k\lt k_i$，则沿指针$p_0$所指的子树继续查找；
• 若$k_i\lt k\lt k_i+1$，则沿着指针$p_i$所指的子树继续查找；
• 若$k\gt k_n$，则沿着指针$p_n$所指的子树继续查找。

6.4.3 B-树的插入

先举个例子，关键字序列为（1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15），创建一棵5阶B-树（下图所有树，有叶子节点的，没画出而已）

将关键字k插入到B-树的过程分两步完成，其过程如下：

• 定位：利用前述的B-树查找算法，找出插入该关键字的最底层中的一个非叶子结点Q；
• 插入：判断该结点Q是否有空位置，插入时分如下两种情况：
  • 不分裂：若Q结点中关键字的个数n满足$n\lt m-1$，表明Q结点还有空位置，在保证结点Q插入前后都有序的情况下，直接把关键字k插入到合适位置；
  • 分裂：若Q结点满足条件$n=m-1$，表明Q结点已没有空位置，需要把结点分裂成两个。

分裂的做法是：（以上图$（c）\to （d）$过程为例）

• 把原结点上的关键字和k按升序排序后， 7， 8， 9， 10， 11， 13
• 从中间位置（$\lceil \frac{m}{2}\rceil$之处）把关键字（除了中间的关键字）分成两部分，左部分包含的关键字放在旧结点中，右部分所包含关键字放在新结点中，
• 旧结点 $\rightarrow[\quad7\quad8\quad]\quad10\quad[\quad11\quad13\quad]\leftarrow$新节点（我理解的分成了3部分，左中右）
• 中间位置的关键字连同新结点的存储位置插入到父结点中，（将$p_i$和10存入父结点）

• 如果父结点的关键字个数也超过m-1，则要再分裂，再往上插，直到这个过程传到根结点为止，这样导致B-树增高一层。（注：分裂不一定导致高度增高一层）

6.4.4 B-树的删除

要使删除结点后的树仍是B-树，则应满足B-树的定义，关键字个数$\ge\lceil \frac{m}{2}\rceil -1$，将涉及结点的合并问题

在B-树上删除关键字k的过程也可分为两步，其过程如下：

• 定位：利用B-树的查找算法找到关键字k所在的节点Q，（与插入不同的是，这里的Q结点不一定是最底层非叶子结点）

• 删除：在Q结点上删除关键字k分两种情况：

  • Q为非最底层的非叶子结点：关键字$k=k_i$，则用$p_i$所指子树中的最小关键字x来替代$k_i$，x必在最底层某个非叶子结点中，从而转化成在最底层非叶子结点上删除关键字。（还是以上面刚生成的5阶B-树为例）

    过程中，关键字16=[13, 16]结点中的16，$p_i$是16右边的指针，指向[17 18 19 20]，其中最小关键字为17， 用17代替16，然后再删除最底层非叶子结点上的关键字17.

    

  • Q为最底层的非叶子结点：又分以下3种情况：

    • 直接删除关键字：若被删除结点的关键字个数大于$\lceil \frac{m}{2}\rceil-1$，表明删去改关键字后仍满足B-树的定义，则可直接删去关键字x；

      比如这里删除关键字8，可直接删除，$m=5,\lceil\frac{m}{2} \rceil-1=3-1=2$；

    • 兄弟够借：若被删除结点的关键字个数等于$\lceil \frac{m}{2}\rceil-1$，表明删去关键字后该结点将不满足B-树的定义。此时，若该结点的左（或右）兄弟结点中关键字个数大于$\lceil\frac m2\rceil-1$，则把该结点的左（或右）兄弟结点中最大（或最小）的关键字向上移到父结点中；

      比如，这里删除15，结点变为[ 14 ]，不满足条件；它的右兄弟结点[ 18 19 20 ]，结点$n\gt \lceil\frac m2\rceil-1$，右兄弟最小的18上移；同时把父结点中大于（或小于）上移关键字的关键字下移到要删除关键字的结点中；18上移后，其父结点变为[ 13 17 18 ]，右小小，17小于18，下移到[ 14 ]变为[ 14 17 ]；

      

    • 兄弟不够借（合并）：假如被删除结点的关键字个数等于$\lceil \frac m2\rceil-1$。此时，需要把删除关键字的结点与其左（或右）兄弟结点以及父结点中分割二者的关键字合并成一个结点。

      比如这里删除4，结点变为[ 5 ]，不满足条件；它的左兄弟结点[ 1 2 ]，关键字个数为$\lceil \frac m2 \rceil-1$，右兄弟结点[ 7 9 ]，关键字个数为$\lceil \frac m2 \rceil-1$，选取父结点中分割二者（这里二者是[ 5 ]与其兄弟[ 1 2 ]）的关键字是3；合并成一个结点，即将[ 1 2 ]，[ 3 ]，[ 5 ]合并为[ 1 2 3 5 ]，合并后其父结点[ 6 ]，不满足条件；它的右兄弟结点[ 13 18 ]，关键字个数为$\lceil \frac m2 \rceil-1$，选取父结点中分割二者（这里二者是[ 6 ]，[ 10 ]，[ 13 18 ]合并成[ 6 10 13 18 ]）

      如果因此使父结点中关键字个数小于$\lceil \frac m2 \rceil-1$，则对此父结点做同样处理，以致可能直到根结点做这样的处理，从而是整个B-树减少一层。

      

例：含有n个非叶子结点的m阶B-树中总共至少包含___个关键字

A. $n(\lceil \frac m2 \rceil-1)$ B. $(n-1)(\lceil \frac m2 \rceil-1)+1$；

注：定义中是除根结点外的非叶子结点至少含有$\lceil \frac m2 \rceil-1$个关键字，根结点至少有一个关键字

具有n个关键字的m阶B-树中共有n+1个叶子结点；

B-树中叶子结点对应查找失败的情况，对具有n个关键字的查找集合进行查找，失败的可能性有n+1种；

• 删除的关键字所在的结点所含关键字个数为关键字个数下限时（$\lceil \frac m2 \rceil-1$），会引起合并；
• 具有n个关键字的m阶B-树中共有n+1个叶子结点。B-树中叶子结点对应查找失败的情况，对具有n个关键字的查找结合进行查找，失败的可能性有n+1种。

6.5 散列表（Hash）表及其查找

在记录的存储位置和它的关键字之间建立一个确定的对应关系H，使每个关键字和表中一个唯一的存储位置（称为哈希地址）相对应，称这个对应关系为哈希（散列）函数，根据这个思想建立的表为哈希表（也称散列表）。

若$key1\ne key2$，而$H(key1)=H(key2)$，则这种现象称为冲突，且$key1$和$key2$对哈希函数H来说是同义词。

哈希表的主要特点是建立了关键字和存储地址之间的直接映射关系。

6.5.1 哈希函数的构造

一个好的哈希函数应使一组关键字的哈希地址均匀分布在整个哈希表中从而减少冲突。

• 直接定址法：$H(key)=key$或$H(key)=a*key+b$；
• 数学分析法：
• 平方取中法：
• 除留余数法：$数p\le 表长m，余数为H(key)=key\ MOD\ P$。

6.5.2 处理冲突的方法

均匀的哈希函数可以减少冲突，但不能避免。

冲突是指由关键字得到的哈希地址处已有记录，而“处理冲突“就是为该关键字的记录找到另一个”空“的哈希地址。

• 开放定址法

  以发生冲突的哈希地址为自变量，通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。

  • 线性探测法

    从发生冲突的地址（设为d）开始，依次探测d的下一地址（当到达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直到找到一个空闲单位为止。递推公式为：$H_i(k)=(H(k)+i)\ MOD\ m(1\le i\le m-1)$；

    不同关键字对同一哈希地址进行争夺的现象称为聚集（或堆积）。

    线性探测法容易产生堆积问题。

  • 平方探测法

    设发送冲突的地址为d，则平方探测法的探测序列为：$d+1^2,d-1^2,d+2^2,d-2^2,...$；

    递推公式为：$H_i=(H(k)+d_i)\ MOD\ m(1\le i\le m-1)$；

    其中，$d_i=i^2,-1^2,2^2,-2^2,...,\pm k^2(k\le \frac{m}{2})$；

    避免堆积，但不能探测到哈希表上的所有单元。

  • 伪随机序列法

  • 双哈希函数法

• 拉链法

6.5.3 哈希表的查找分析

哈希表的查找效率（比较次数）取决于：哈希函数、处理冲突的方法和哈希表的装填因子。与长度，关键字个数无关。

哈希表的装填因子定义为$\alpha = \frac{表中填入的记录数}{哈希表的长度}=\frac{n}{m}$；

其中$\alpha$标志着哈希表的装满程度。$\alpha$越小，发生冲突的可能性越小，查找效率越高。

哈希表的平均查找长度是$\alpha$的函数；

采用线性探测的哈希表查找成功时的平均查找长度为$\frac{1}{2}*(1+\frac{1}{1-\alpha})$；

采用拉链法的哈希表查找成功时的平均查找长度为$1+\frac{\alpha}{2}$；

假定有k个关键字互为同义词，若用线性探测法，把这k个关键字填入哈希表中，至少要进行$\frac{k*(k+1)}{2}$次探测，$1+2+3+...+k=\frac{k(k+1)}{2}$；

6.6 查找算法的分析及应用

七、内部排序

7.1 排序的基本概念

所谓排序，就是要整理表中的元素，使之按关键字递增（或递减）有序排序。

• 排序算法的稳定性

  排序后，具有相同关键字的元素之间的相对次序保持不变或发生变化。

• 内排序和外排序

  在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称为外排序。例如拓扑排序就是外排序。

• 正序和反序

• 排序的分类

• 基于比较的排序算法的性能

  基于比较的排序算法中，主要进行两种基本操作：比较和移动，排序算法的性能由算法的时间和空间确定，而时间是有 比较和移动的次数确定。

7.2 插入排序

按其关键字的大小插入到已经排序的有序区中的适当位置上。

7.2.1 直接插入排序

其过程是依次将无序区中每个元素插入到一个有序区中。

例如，取一个中间过程，7 8 9 | 6 5 4 3 2 1 0，先把即将进行排序的关键字6存起来，然后循环将6之前的元素9，8，7依次与6比较，如果比6大，向后移一位，9到6的位置，8到9，7到8，然后将6插在原来7的位置上。

7.2.2 折半插入排序（二分插入排序）

折半查找然后插入排序，有序区，有序，对有序区进行二分查找。

思想还是比较，找位置，元素后裔，根据位置插入。

7.2.3 希尔（shell）排序（缩小增量排序方法）

把记录按下标的一定增量d分组（通常$d=\frac{n}{2}$），对每组记录采用直接插入排序方法进行排序，随增量d逐渐减小（$d=\frac{d}{2}$），所分成的组包含的记录越来越多，到$d=1$时，整个数据合成一组，完成排序。

7.3 交换排序

发现这两个元素的次序相反时即进行交换，直到没有反序的元素为止。

7.3.1 冒泡排序

从最下面的元素开始，对每两个相邻的关键字进行比较，且使关键字较小的元素换至关键字较大的元素之上，使得经过一趟冒泡排序后，关键字最小的元素到达最上端。

7.3.2 快速排序

在待排序的n个元素中任取一个元素（通常是第一个元素）作为基准，将后面的数与之比较，比它小的从头依次往后存放，比它大的从尾依次往前存放。最终该基准会放在最终位置上，数据序列被此元素划分成两部分，称为一趟快速排序，再对左右部分进行同样的过程。

7.3.3 选择排序

每一趟从待排序的元素序列中选出关键字最大（或最小）的元素，按顺序放在已排序的元素序列的最后面（或最前面），直到全部排完为止。

7.3.4 简单选择排序

0 1 2 3 | 6 8 9 7 4 5（前面有序区，后面无序区）

从无序区中选一个最小的元素4将其与无序区第一个元素6交换，有序区元素加1，无序区元素减1；经过一趟后：

0 1 2 3 4 | 8 9 7 6 5

7.4 堆排序

堆排序是一种树形选择排序方法，在排序过程中，将序列看成一棵完全二叉树的顺序存储结构。

堆的定义：n个关键字序列$k_1,k_2,...,k_n$称为堆，当且仅当该堆序列满足如下性质：

   k
 /   \
k2i  k2i+1

• $k_i \leq k_{2i}且k_i \leq k_{2i+1}$；
• 或$k_i \geq k_{2i}$且$k_i \geq k_{2i+1},(1 \leq i \leq \lfloor\frac{n}{2} \rfloor)$；

满足第1种情况的堆称为小根堆，满足第2种情况的堆称为大根堆。

例，设待排序的表有10个元素，其关键字分别为$(6,8,7,9,0,1,3,2,4,5)$，说明采用堆排序方法进行排序的过程。

在初始堆$R[0,...,n-1]$构造好以后，根结点$R[0]$一定是最大关键字结点。将其放在序列的最后，也就是与最后一个叶子交换，最大元素归位。$R[1,...,n-2]$不一定为堆，但其左右子树为堆，再用一次shift算法，将这n-1个结点调成堆。

• 每一趟排序后，堆元素个数减1；
• 筛选调整结果仍为大根堆；
• 调整后根与最底层最右边的叶子交换。

7.5 归并排序

将2个或多个有序子表归并成一个子表。

二路归并排序

例，设待排序的表有10个元素，其关键字分别为$(6,8,7,9,0,1,3,2,4,5)$，说明采用二路归并排序方法进行排序的过程。

在采用二路归并排序时需要进行$\lceil log_2n \rceil$趟归并排序，其过程如下图，称之为归并树，其高度为5。

• 第一趟，每个元素是一个子表，子表两两归并；
• 第一趟排序时，(6)，(8)相邻有序表，进行归并，每次从两个表中取出1个元素进行关键字比较，将较小者放入$R_1$中，最后将各表中余下的部分直接复制到$R_1$中。这样$R_1$有序，再复制到R中。
• 每对连在一起，组成一对有序表组。
• 在调用Merge()将相邻的一对子表进行归并时，必须对表的个数可能是奇数以及最后一个子表的长度小于length这两种特殊情况进行特殊处理；若子表的个数为奇数，则最后一个子表无需和其他子表归并（即本趟轮空），比如这里5个子表，最后(4,5)子表第1趟，第2趟轮空；若子表的个数为偶数，则要注意到最后一对子表中后一个子表的区间上界n-1。

7.7 基数排序

基数的定义，十进制数的基数为10，$r=10$。

适合一些特别的场合，如扑克牌排序问题，按照“基排”的思想，不用进行关键字比较的。

在基数排序过程中共进行了d趟的分配和收集。每一趟中分配过程需要扫描所有结点，而收集过程是按队列进行的，所以一趟的执行时间为$O(n+r)$，因此基数排序的时间复杂度为$O(d*(n+r))$。

在基数排序过程中第一趟排序需要的辅助存储空间为r（创建r个队列），但以后的各趟排序中重复使用这些队列，所以总的辅助空间复杂度为$O(r)$。

另外，在基数排序中使用的是队列，排在后面的元素只能排在前面相同关键字的后面，相对位置不会发生改变，稳定排序方法。

7.8 各种内部排序算法的比较

分类	排序方法	时间复杂度			空间复杂度	稳定性
		最坏情况	最好情况	平均情况
插入排序	直接插入排序	$$O(n^2)$$	$$O(n)$$	$$O(n^2)$$	$$O(1)$$	稳定
	折半插入排序	$$O(n^2)$$	$$O(n)$$	$$O(n^2)$$	$$O(1)$$	稳定
	希尔排序			$$O(n^{1.3})$$	$$O(1)$$	不稳定
交换排序	冒泡排序	$$O(n^2)$$	$$O(n)$$	$$O(n^2)$$	$$O(1)$$	稳定
	快速排序	$$O(n^2)$$	$$O(n*log_2n)$$	$$O(n*log_2n)$$	$$O(log_2n)$$	不稳定
选择排序	简单选择排序	$$O(n^2)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	不稳定
	堆排序	$$O(n*log_2n)$$	$$O(n*log_2n)$$	$$O(n*log_2n)$$	$$O(1)$$	不稳定
	二路归并排序	$$O(n*log_2n)$$	$$O(n*log_2n)$$	$$O(n*log_2n)$$	$$O(1)$$	稳定
	基数排序	$$O(n+r)$$	$$O(n+r)$$	$$O(n+r)$$	$$O(r)$$	稳定

简单选择排序：
比较次数：$O(n^2)$
移动次数：$O(n)$
二路归并排序：与初始序列无关

7.9 内部排序算法的应用

八、参考书目

从考试大纲看，所要求的知识在一般的大学数据结构教材中都已经包含，所以，选择哪本书并不是重要的事情。我们推荐清华大学出版社的《数据结构（第二版）》（严蔚敏主编）。这本书有多种语言的版本，建议选择C语言的版本，在复习的过程中，还可以配以相应的习题集。