数据结构·

一、整体要求·

  1. 数据的逻辑结构与存储结构的基本概念
  2. 数据结构算法的定义、基本原理和性质，理解算法分析的基本概念，包括采用大 O 形式表示时间复杂度和空间复杂度;

二、知识要点·

1.数据结构概述·

(1) 数据的逻辑结构与存储结构的基本概念

  • 数据结构三要素：逻辑结构、存储结构与数据的运算。

    ① 逻辑结构

    逻辑结构指数据元素之间存在的逻辑关系，是固有的客观联系；

    逻辑结构分为线性结构与非线性结构，比如：线性表、树、图等；

    ② 存储结构

    ​ 存储结构又称为物理结构，指数据结构在计算机中的表示（映像），是计算机内部的存储方法；

    ​ 存储结构主要有顺序存储、链式存储、索引存储和散列存储；

    ​ 一种逻辑结构通过映像便可以得到它的存储结构；

    ​ 诸如顺序表、哈希表、链表这样的表述，它们既体现了逻辑结构（均为线性），又体现了存储结构（顺序、散列、链式）；

    ​ 而这样的表述我们往往就直接称之为数据结构；

    ​ 诸如有序表，它只体现了逻辑结构（线性），而存储结构是未知的（可以是顺序、链式……）；

    ​ 不存在只体现存储结构而不体现逻辑结构的表述；

    ​ 所以，我们认为：逻辑结构独立于存储结构。

    ③ 数据的运算（算法）

    算法包括运算的定义（取决于逻辑结构，体现算法功能）与实现（取决于存储结构，体现于操作步骤）。

(2) 算法的定义、基本性质以及算法分析的基本概念，包括采用大 O 形式表示时间复杂度和空间复杂度。

  • 算法的 5 个重要特性：有穷性、确定性、有效性（可行性）、输入与输出；

  • 一个好的算法的目标：正确性、可读性、鲁棒性、高效率与低存储量需求。

  • 时间复杂度指算法所有语句被重复执行次数总和的数量级。是算法在最坏情况下的时间消耗。

    常见时间复杂度比较：

    O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

  • 空间复杂度指算法耗费存储空间的数量级。是算法在最坏情况下所使用的额外空间。

  • 例：

1
2
3
4
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

对于递归函数，直接得 T(n) = 1 + T(n - 1) = k + T(n - k) = n - 1 + T(1) = n，即 T(n) = O(n)。

2.线性表·

(1) 线性关系，线性表的定义，线性表的基本操作·

  • 线性表是具有相同数据类型的 n 个数据元素的有限序列。

  • 线性表的特点：

    ① 表中元素具有逻辑上的顺序性，有先后次序；

    ② 表中元素都是数据元素，每个元素都是单个元素；

    ③ 表中元素的数据类型都相同，占有相同大小的存储空间；

    ④ 表中元素具有抽象性，即仅讨论元素间的逻辑关系，不考虑具体内容。

    ​ ⑤ 表中元素个数有限。

  • 线性表是逻辑结构，表示元素一对一的相邻关系；

  • 顺序表、链表是存储结构，表示在计算机中数据的存储方式。

(2) 线性表的顺序存储结构·

  • 线性表的顺序存储又称顺序表，用一组地址连续的存储单元存储；
  • 顺序表是一种随机存取的存储结构，存储密度大；
  • 一般用数组表示顺序表，但线性表从 1 开始，数组下标从 0 开始；
  • 顺序表最主要特点是随机访问，通过首地址与元素序号在 O(1) 找到指定元素。
  • 插入结点 O(n)，删除结点 O(n)，按值查找 O(n) 按序查找O(1)

(3) 线性表的链式存储结构(包括线性链表、循环链表和双向链表)的构造原理·

线性链表

  • 线性表的链式存储又称单链表或者线性链表，用一组任意的存储单元来存储数据元素；

  • 头指针用以标识单链表，如果其值为 NULL，说明为一个空表；

  • 在第一个结点前附加一个结点，成为头结点，可以不记录信息，也可以记录表长。

  • 设置头结点，便于空表与非空表的统一处理。

  • 建表 O(n)

    ​ ①头插法：将存有读入数据的新结点插入到当前链表表头；

    使用头插法会导致读入数据与生成链表顺序相反；

    ②尾插法：增加一个尾指针，以使新结点直接插入到表尾。

  • 查找 O(n)

    ​ ① 按序号查找

    ② 按值查找

  • 插入结点 O(n)

    一般指在某结点的后面插入新结点，即后插操作。

  • 删除结点 O(n)

  • 求表长 O(n)

  • 双链表：在单链表基础上增加前驱指针。

  • 循环链表

    ​ 对于循环单链表，尾结点指针不是指向 NULL，而是头结点；

    ​ 对于循环双链表，在循环单链表基础上，头结点的前驱指针指向尾结点。

(4) 在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)

3.数组·

(1) 一维数组和二维数组的存储

  • 数组是由 n 个相同类型的数据元素构成的有限序列。
  • 数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素均为定长线性表的线性表。
  • 对于多维数组有两种映射方法：按行优先与按列优先。一般默认按行优先

(2) 矩阵的压缩存储的基本概念

  • 压缩存储：多个值相同的元素只分配一个存储空间，0 元素不分配；

(3) 对称矩阵、对角矩阵的压缩存储

(4) 稀疏矩阵的三元组表表示

  • 稀疏矩阵指非零元素个数远小于零个数的矩阵。
  • 用**三元组（行，列，值）**来存储，或者十字链表法。

4.堆栈与队列·

(1) 堆栈与队列的基本概念与基本操作·

  • 栈是一种操作受限的线性表，只允许在一端进行插入或删除操作。”后进先出“
  • 数学性质：n 个不同元素进栈，出栈元素不同排列的个数为 C2nn/(n+1)C_{2n}^n / (n + 1)，这就是卡特兰数。
  • 队列也是一种操作受限的线性表，只允许在表的一端插入，另一端删除的线性表。“先进先出”

(2) 堆栈的顺序存储结构与链式存储结构的构造原理·

  • 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
1
2
3
4
5
6
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{
    ElemType data[MAXSIZE];
    int top;    //用于栈顶指针
}SqStack;

  • 共享栈：两个顺序栈共享一个一维数组，栈底分别设在两端，栈顶向中间延伸。

  • 采用链式存储的栈称为链栈。

    • 优点：便于多个栈共享存储空间，提高效率，且不存在栈溢出的情况。
    • 链栈没有头结点，直接指向栈顶元素。

(3) 队列顺序存储结构与链式存储结构的构造原理·

  • 队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。
  • 循环队列：普通队列会出现假溢出情况，故引用循环队列，将队列从逻辑上视为一个环，利用取余运算实现。
  • 由于循环队列在队空与队满的判断条件是等价的，故需要一些处理方式来区分：
    • 牺牲一个单元来区分，约定“队头在队尾下一位置作为队满的标志”；
    • 增设表示元素个数的数据成员。
  • 队列的链式存储：采用链式存储的队列称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。
  • 链队列往往设计成带头结点的单链表。

(4) 在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计

(5) 堆栈和队列在解决实际问题中应用·

  • 栈在括号匹配中的应用

  • 栈在表达式求值中的应用

    • 后缀表达式可以轻松获得运算符关系，且不用处理括号。用栈处理。

  • 栈在递归中的应用

    • 可以用栈来模拟递归过程，以消除递归。
    • 对于同一个问题，非递归算法效率通常比递归算法更高。

  • 队列在层次遍历中的应用

    • 比如 BFS

  • 队列在计算机系统中的应用

    • 比如页面替换算法

5.树与二叉树·

(1) 树与二叉树的基本概念、基本特征和名词术语·

  • 树是 n 个结点的有限集。对于任意一棵空树，满足：

    ​ ① 有且仅有一个特定的根结点；

② n > 1 时，除去根结点外的其他结点又可分为若干个互不相交的子树。

  • 度：结点的孩子个数为结点的度；最大结点的度为树的度

  • 深度（自顶向下） / 高度（自底向上）

  • 森林：m 棵互不相交的树集合，加上一个共同根结点后即可认为是一棵树

  • 树的性质

    ① 树的结点数 = 所有结点度数之和 + 1；

    ② 度为 m 的树第 i 层至多 m(i−1)m^{(i-1)} 个结点；

    ③ 高度为 h 的 m 叉树至多 (mh−1)/(m−1)(m^h - 1) / (m - 1) 个结点；

    ④ 具有 n 个结点的 m 叉树最小高度为 logm[n(m−1)+1]log_m[n(m-1) + 1] 向上取整。

(2) 完全二叉树与满二叉树·

基本概念，二叉树的基本性质及其应用

  • 二叉树是度不大于 2 的有序树，即每个结点至多 2 棵子树，且有左右之分；
  • 满二叉树：高度为 h 且含有 2h−12^h - 1 个结点的二叉树；

对于编号为 i 的结点，左孩子为 2i2i，后孩子为 2i+12i + 1。

  • 完全二叉树：最后一层可以不含有最多结点的满二叉树；
  • 还有二叉排序树与平衡二叉树也是特殊的二叉树。
  • 二叉树的性质
    • 非空二叉树叶子结点数 = 度为 2 的结点数 + 1（常用结论）
    • 在二叉树的第 i 层上至多有2i−12^{i-1}个结点（i>=1）
    • 深度为 k 的二叉树至多有2k−12^k-1个结点（k>=1）
    • 包含 n 个节点的二叉树的高度至少为**log2(n+1)log_2 (n+1)**

(3)二叉树的顺序存储结构与二叉链表存储结构的基本原理·

  • 二叉树的顺序存储结构
    • 一般只用于满二叉树与完全二叉树，否则太浪费空间；
    • 数组下标从 1 开始更恰当，以满足父子结点之间的编号关系。
  • 二叉树的链式存储结构
    • 每个结点包含结点值、指向左孩子结点的指针、指向右孩子结点的指针。

(4) 二叉树的遍历·

二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用

  • 前序遍历：先根结点，再左子树，再右子树。

  • 中序遍历：先左子树，再根结点，再右子树。

  • 后序遍历：先左子树，再右子树，再根结点。

  • 按层次遍历：以满二叉树/完全二叉树按层次编号的顺序进行遍历。

  • 递归问题的非递归算法的设计

    ​ 即用栈来模拟递归的过程；

    ​ 效率更高，但编写起来更麻烦。

(5) 二叉排序树·

基本概念、建立(插入)、查找以及平均査找长度(ASL)的计算

  • 二叉排序树的定义
    • 二叉排序树的左子树所有结点小于根结点，右子树所有结点大于根结点；
    • 二叉排序树的中序遍历必然严格单调递增。
  • 二叉排序树的删除，删除结点如果：
    • 右子树空，则用左儿子结点填补；
    • 左子树空，则用右儿子结点填补；
    • 左右子树均非空，则用右子树的中序序列的第一个结点填补。
  • 二叉排序树的查找
    • 如果左右子树高度差不超过 1（即平衡二叉树），则平均查找长度为 O(log2n)O(log_2n)
    • 如果是一棵单支树（即类似于单链表），则为 O(n)O(n)

(6) 堆·

  • “优先队列” （Priority Queue）是特殊的“队列”，从堆中取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。采用完全二叉树存储的优先队列称为堆（Heap）。

  • 根据父子结点大小关系，二叉堆可以分成两类：

    ​ > 大根堆：结点权值小于等于父亲结点权值(只是保证父节点比子节点大，不能保证像二叉搜索树那样右边比左边大)

    ​ > 小根堆：结点权值大于等于父亲结点权值

(7) 哈夫曼树及其应用·

  • 哈夫曼树的基本概念

    • WPL：树中所有叶结点带权路径长度（路径长度 * 结点权值）之和；
    • 对于 n 个带权叶结点构成的所有二叉树中，WPL 值最小的为哈夫曼树。

  • 哈夫曼树的构造

    • 每次选取两棵根结点权值最小的树作为新结点的左右子树，以此反复；
    • 哈夫曼树没有度为 1 的结点。

  • 哈夫曼编码

6.图·

(1) 图的基本概念、名词术语·

  • 图记为G(V,E)，V是顶点集，E是边集。图至少有一个顶点，可以没有边。

  • 名词术语

    ① 有向图：边集由有向边（弧）构成；

    ② 无向图：边集由无向边（边）构成；

弧一般用 <> 表示，边一般用 () 表示；

​ ③ 简单图：没有重边，没有自环；否则为多重图；

④ 完全图：任意两点之间都存在边（或者两条方向相反的弧）无向完全图的边数为n(n−1)/2n(n-1)/2；

⑤ 子图：边集与点集均为另一个图的子集；

当点集相等时，则称为生成子图；

⑥ 无向图的连通、连通图、连通分量：

​ 连通图：任意两个顶点之间都有路径的图。

极大连通子图（连通分量）：对于连通图，极大连通子图即其自身；对于非连通图，有多个极大连通子图；

极小连通子图：即生成树，对于非连通图没有意义；

⑦ 有向图的强连通、强连通图、强连通分量：

​ 强连通图：有向图的任意两个顶点之间都有路径。

极大强连通子图：又称为强连通分量，类比于连通分量；

不存在极小强连通子图；

⑧ 生成树：包含全部顶点(n)的极小连通子图，边数是n-1；

⑨ 度、入度、出度：顶点v的度是指依附于顶点v的边的条数；

⑩ 网：带权图的别称；

⑪ 稠密图、稀疏图：均为模糊而相对的概念；

考点：

  • 对于n个顶点的无向图G，
    • 所有顶点的度之和=2|E|
    • 若G是连通图，则最少有n-1条边（树）， 若|E|>n-1，则一定有回路
    • 若G是非连通图，则最多可能有 Cn−12C_{n-1}^{2}条边 无向完全图共有Cn2C_{n}^{2} 条边
  • 对于n个顶点的有向图G，
    • 所有顶点的出度之和=入度之和=|E| 所有顶点的度之和=2|E|
    • 若G是强连通图，则最少有n条边（形成回路）
    • 有向完全图共有条2Cn22C_{n}^{2}边

(2) 图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点·

邻接矩阵存储方法

  • 用二维数组表示图，数组角标表示顶点编号，数组元素的值表示边的有无或者权。
  • 图的邻接矩阵唯一，无向图的邻接矩阵对称。
  • 稠密图适合用邻接矩阵存储，无向图的矩阵可以压缩存储。

邻接表存储方法

  • 表示方法：所有邻接于顶点viv_i的顶点vjv_j链成单链表，再用一维数组作为顶点表就构成了图的邻接表。
  • 邻接表法适合稀疏矩阵。
  • 图的邻接表不唯一。
  • 找到某顶点所有的边（或者说所有邻接顶点）需要的时间： 邻接矩阵 O(V)O(V) ；邻接表法 O(E)O(E)。

图的存储方法还有：十字链表、邻接多重表

(3) 图的深度优先搜索与广度优先搜索·

深度优先遍历DFS·

时间复杂度:采用邻接矩阵存储结构时，查找所有顶点的邻接点所需时间为**O(∣V∣2)O(|V|^2); 而采用邻接表时，找邻接点所需时间为O(∣E∣)O(|E|)。因此，DFS的时间复杂度为O(∣V∣+∣E∣)O(|V|+|E|)** 对不连通图，一次调用DFS算法只可以遍历一个连通分量。

1
2
3
4
5
6
7
8
9
10
11
/* Visited[]为全局变量，已经初始化为false */
void DFS(LGraph Graph,Vertex V)
{/* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
	Visit(V);/* 访问第V个顶点 */
	Visited[V]=true;/* 标记V已访问 */
	for(PtrToAdjVNode W=Graph->G[V].FirstEdge;W;W=W->Next){/* 对V的每个邻接点W->AdjV */
		if(!Visited[W->AdjV]){/* 若W->AdjV未被访问 */
			DFS(Graph,W->AdjV);/* 则递归访问之 */
		}
	}	
}
广度优先遍历BFS·

复杂度同DFS。即**O(∣V∣2)O(|V|^2)**或者O(∣V∣+∣E∣)O(|V|+|E|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Visited[]为全局变量，已经初始化为false */
void BFS(MGraph Graph,Vertex S)
{/* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 ,void(*Visit)(Vertex)*/
	Queue Q = CreateQueue();/* 创建空队列, MaxSize为外部定义的常数 */
	/* 访问顶点S：此处可根据具体访问需要改写 */
	Visit(S);
	Visited[S]=true;
	AddQ(Q,S);
	while(!IsEmpty(Q)){
		Vertex V = DeleteQ(Q);
		for(Vertex W=0;W<Graph->Nv;W++){/* 对图中的每个顶点W */
			/* 若W是V的邻接点并且未访问过 */
			if(!Visited[W] && IsEdge(Graph,V,W)){
				/* 访问顶点W */
				Visit(W);
				Visited[W]=true;
				AddQ(Q,W);
			}
		}
	}
}

(4) 最小生成树MST·

Prim算法·

邻接矩阵O(V2)O(V^2)

邻接表+堆优化O(ElogV)O(ElogV)

Kruskal算法·

O(E∗logV)O(E*logV)

从小到大收录边，使用最小堆依次弹出边。

对于每条边，使用并查集验证是否成环，不成环则收录进去。

也可以先用快排对边进行排序，然后按顺序使用并查集处理即可。

(5) 最短路径、AOV 网与拓扑排序的基本概念·

Dijkstra算法·

单源最短路，不能有负值边。

邻接矩阵O(V2)O(V^2)

邻接表+堆优化O(ElogV)O(ElogV)

Floyd算法·

多源最短路 O(V3)O(V^3)

7.文件及查找·

ASL: 平均查找长度

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n,Ci是找到第i个元素的比较次数，

ASL=∑i=1npici{ASL=\sum_{i=1}^np_ic_i}

(1) 顺序查找法以及平均查找长度(ASL)的计算

一般线性表的顺序查找：

​ 查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。若每个元素查找概率相同，则：

ASL成功=(n+1)/2ASL_{成功}=(n+1)/2

(2) 折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造

ASL=1n∑i=1nli=1n(1×1+2×2+⋯+h×2h−1)=n+1nlog⁡2(n+1)−1≈log⁡2(n+1)−1\mathrm{ASL}=\frac{1}{n}\sum_{i=1}^{n}l_{i}=\frac{1}{n}(1\times1+2\times2+\cdots+h\times2^{h-1})=\frac{n+1}{n}\log_{2}(n+1)-1\approx\log_{2}(n+1)-1

(3) 杂凑表的构造、杂凑函数的构造，杂凑碰撞的基本概念、处理杂凑碰撞的基本方法以及杂凑表的查找和平均查找长度的计算

8.内排序·

(1) 排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算

(2) 插入排序法(含折半插入排序法)·

i 前边都是有序的，a[i]跟前边比，插入到合适的位置。

过程如下：a[0]及之前有序的，a[1]跟a[0]比，插入之后a[1]及之前都有序了；a[2]跟a[1]、a[0]比，插入之后a[2]之前都有序了……【a[2]<a[1]，a[1]要向后移，a[2]向前移跟a[0]比，a[2]<a[0]，a[0]向后移；a[2]>=a[0]，a[2]就找到了合适的位置】

外循环遍历1 -> n-1，内循环从后向前找合适的位置，可能需要数组元素的向右移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 插入排序 */
void Insert_Sort(int a[],int n)
{
	int p;
	for(p = 1; p < n; p++){
		int tmp=a[p];/*取出未排序序列中的第一个元素*/
		int i;
		for(i=p;i>=1&&a[i-1]>tmp;i--){
			a[i]=a[i-1];/*依次与已排序序列中元素比较并右移*/
		}
		a[i]=tmp;/*放进合适的位置 */
	}
}

(3) 选择排序法·

每次从第i个数到第n个数中找到最小的元素，将这个元素和第i个位置上的元素交换。时间复杂度显然为 O(n2)O(n ^ 2)。

1
2
3
4
5
6
7
8
9
10
11
12
/*选择排序*/
void Select_Sort(int a[],int n)
{
	int i,j,min;
	for (i = 0; i < n; i++){
		min = i;
		for ( j = i+1; j < n; j++) /*寻找最小元素*/
			if(a[j] < a[min])
			min = j;  /*min记录最小元素*/ 
		swap(&a[i], &a[min]);	/*交换*/ 	 			
	}	
}

(4) 冒泡排序法·

从第 1 位开始扫描，检查相邻的两个元素，如果前一个元素大于后一个元素，则交换两个元素的位置，一直扫描到第 n 位。扫描完后，能且仅能确定第 n 个元素为整个序列的最大值，则下一轮扫描为从第 1 位到第 n - 1 位，并确定第 n - 1 位为倒数第二大元素，以此类推，扫描 n - 1 次后，完成排序。

1
2
3
4
5
6
7
8
void BubbleSort(int *array, int n){
	for (int i = 0; i < n; i++ ){
		for (int j = 0; j < n - i - 1; j++){
			if (array[j] > array[j+1])
				swap(&array[j] , &array[j+1]);
		}
	}
}

(5) 希尔排序法·

希尔排序是n-间隔的插入排序。

希尔排序算法的整体时间复杂度和增量序列的选取有关，目前并没有统一的最优增量序列。

当使用增量序列 { ⌊N/2⌋, ⌊N/2^2⌋ , …, 1} 进行希尔排序时，最差情况下的时间复杂度 Tworst(n) = O(N^2)；

当使用增量序列 { 2k-1,…, 7, 3,1 } 时，最差情况下时间复杂度为 Tworst(n) = O(N3/2)，平均时间复杂度为Taverage(n) = O(N5/4)。

希尔排序不是稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 希尔排序 - 用Sedgewick增量序列 */
void Shell_Sort(int a[],int n)
{
	/* 这里只列出一小部分增量 */
	int Sedgewick[]={929,505,209,109,41,19,5,1,0};
	
	int si;
	for(si=0;Sedgewick[si]>=n;si++)
		; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
	
	int D,i,p;
	for(D=Sedgewick[si];D>0;D=Sedgewick[++si]){
		for(p=D;p<n;p++){ /* 插入排序*/
			int tmp=a[p];
			for(i=p;i>=D&&a[i-D]>tmp;i-=D){
				a[i]=a[i-D];
			}
			a[i]=tmp;
		}
	}
}

(6) 快速排序法·

设置一个基准e，把比e小的都交换到前边，比e大的都交换到后边，然后放入e。此时e就是他应该在的位置。之后递归的处理e的左右两边。快速排序每一轮都能把一个元素放在他最后应该在的位置。

快速排序不是稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void qsort(int v[ ],int left, int right)
{
    int i, j,last;
    if(left >= right) return;
    swap(&v[left], &v[(left+right)/2]); //move partition elem to v[0] 
    i=left;
    j=right+1;
    while(1) {
    	while(v[++i]<v[left]){}  //a[i]>=pri
		while(v[--j]>v[left]){}  //a[j]<=pri
		if(i<j){
			swap(&v[i],&v[j]);
		}
		else{
			break;
		}
	}
    //i>=j了，a[j]<=a[left]，所以跟a[j]互换，把a[j]换到a[left]，因为a[j]小于a[left]
	swap(&v[j],&v[left]);
    qsort(v, left, j-1);  
    qsort(v, j+1, right);
}

(7) 堆积排序法·

优化选择排序，不需要遍历去找最小值，而是使用堆来找最大/小值。

n个数构建最大/小堆的算法是O(n)的。

【一种朴素的方法是：构成最小堆之后，每次弹出最小值，弹出n次，即有序】

时间复杂度为 O(n log n)。