1. 数据结构理论

1.1数据

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。

1.2数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

1.3算法的概念

算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。
对于算法而言，语言并不重要，重要的是思想。

1.3.1算法和数据结构区别

数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。

l 算法是为了解决实际问题而设计的。
l 数据结构是算法需要处理的问题载体。
l 数据结构与算法相辅相成

1.3.2 算法的比较

   现在我们需要写一个求1 + 2 + 3 + … + 100的结果程序，你应该怎么写呢？<br />       大多数人马上回写出下面C语言代码（或者其他语言）<br />              var i int<br />              sum := 0<br />              n := 100<br />              for i = 0; i <= n; i++ {<br />                     sum = sum + i<br />              }<br />              fmt.Printf("%d", sum)<br />当然，如果这个问题让高斯来去做，他可能会写如下代码：<br />       sum := 0<br />       n := 100<br />       sum = (1+n)*n/2<br />       fmt.Printf("%d",sum)<br /> <br />很显然，不论是从人类还是计算机的角度来看，下列的算法效率会高出很多，这就是一个好的算法会让你的程序更加的高效。

1.3.3 算法的特性

算法具有五个基本的特性：输入、输出、有穷性、确定性和可行性

输入输出：算法具有零个或多个输入、至少有一个或多个输出。

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性：算法的每一步骤都有确定的含义，不会出现二义性。

可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

1.4 数据结构分类

按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

1.4.1 逻辑结构

1.4.1.1集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。各个数据元素是平等的。他们共同属于同一个集合，数据结构中的集合关系类似于数学中的集合，如下图所示

1.4.1.2线性结构：线性结构中的数据元素之间是一对一的关系。如图：

1.4.1.3树形结构：树形结构中是数据元素之间存在一种一对多的层次关系，如图：

   ![](https://cdn.nlark.com/yuque/0/2020/png/309858/1592293015997-5376289c-8991-480b-9c4f-86b0a2e14b7c.png#height=175&width=396)

1.4.1.4 图形结构： 图形结构的数据元素是多对多的关系，如果：

1.4.2 物理结构

说完了逻辑结构，再说下物理结构，也有的书称为存储结构。
物理结构：是指数据的逻辑结构在计算机中的存储形式，共分为两种：顺序存储和链式存储。

1.4.2.1 顺序存储：是把数据元素存放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的，如图：

如果所有数据结构都很简单有规律，一切就好办了，可实际上，总有人想要插队，或者放弃排队，所以元素集合中就会添加、删除掉成员，显然面对这样时常要变化的结构，顺序存储是不科学的，那怎么办呢

1.4.2.2链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关数据的位置。如图：

   ![](https://cdn.nlark.com/yuque/0/2020/png/309858/1592293016615-5f1ed7bd-3c92-46de-ad20-eff42b9e1a38.png#height=261&width=319)<br /> 

2.线性表

2.1线性表基本概念

线性结构是一种最简单且常用的数据结构。线性结构的基本特点是节点之间满足线性关系。本章讨论的动态数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个开始节点和终端节点。按这种关系，可以把它们的所有节点排列成一个线性序列。但是，他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。
线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同
例：先来看一个大家感兴趣的话题，一年里的星座列表，是不是线性表呢？如图所示：


线性表的性质：
1）a0 为线性表的第一个元素，只有一个后继。 2）an 为线性表的最后一个元素，只有一个前驱。 3）除 a0 和 an 外的其它元素 ai，既有前驱，又有后继。 4）线性表能够逐项访问和顺序存取。

线性表的抽象数据类型定义：

2.2线性表的顺序存储

通常线性表可以采用顺序存储和链式存储。这节课我们主要探讨顺序存储结构以及对应的运算算法的实现。
采用顺序存储是表示线性表最简单的方法，具体做法是：将线性表中的元素一个接一个的存储在一块连续的存储区域中，这种顺序表示的线性表也成为顺序表。

2.2.1线性表顺序存储(动态数组)的设计与实现

操作要点:
l 插入元素算法
n 判断线性表是否合法
n 判断插入位置是否合法
n 判断空间是否满足
n 把最后一个元素到插入位置的元素后移一个位置
n 将新元素插入
n 线性表长度加1
l 获取元素操作
n 判断线性表是否合法
n 判断位置是否合法
n 直接通过数组下标的方式获取元素
l 删除元素算法
n 判断线性表是否合法
n 判断删除位置是否合法
n 将元素取出
n 将删除位置后的元素分别向前移动一个位置
n 线性表长度减1
l 元素的插入


l 元素的删除


注意: 链表的容量和链表的长度是两个不同的概念

2.2.2优点和缺点

Ø 优点：

Ø 缺点：

2.3线性表的链式存储(单向链表)

前面我们写的线性表的顺序存储(动态数组)的案例，最大的缺点是插入和删除时需要移动大量元素，这显然需要耗费时间，能不能想办法解决呢？链表。
链表为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。




l 单链表
n 线性表的链式存储结构中，每个节点中只包含一个指针域，这样的链表叫单链表。
n 通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起（如图）。

l 概念解释：
n 表头结点
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
n 数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
n 尾结点
链表中的最后一个数据结点，其下一元素指针为空，表示无后继。

2.3.1线性表的链式存储(单项链表)的设计与实现

Ø 插入操作

Ø 删除操作

2.3.2优点和缺点

Ø 优点：

Ø 缺点：

3.栈与队列

3.1栈(Stack)

3.1.1栈的基本概念

Ø 概念：
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
Ø 特性
它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
Ø 操作
n 栈的插入操作，叫做进栈，也成压栈。类似子弹入弹夹（如下图所示）
n 栈的删除操作，叫做出栈，也有的叫做弾栈，退栈。如同弹夹中的子弹出夹（如下图所示）

3.1.2栈的顺序存储

Ø 基本概念
栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序表中的位置。
Ø 设计与实现
因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。

3.1.3栈的链式存储

Ø 基本概念
栈的链式存储结构简称链栈。
思考如下问题：
栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？
由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。
Ø 设计与实现
链栈是一种特殊的线性表，链栈可以通过链式线性表来实现。

3.1.4栈的应用(案例)

3.1.4.1函数调用模型

栈是嵌套调用机制的实现基础

3.1.4.2就近匹配

几乎所有的编译器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？如下字符串:
5+5(6)+9/31)-(1+3(
Ø 算法思路
从第一个字符开始扫描
当遇见普通字符时忽略，
当遇见左括号时压入栈中
当遇见右括号时从栈中弹出栈顶符号，并进行匹配
匹配成功：继续读入下一个字符
匹配失败：立即停止，并报错
结束：
成功: 所有字符扫描完毕，且栈为空
失败：匹配失败或所有字符扫描完毕但栈非空
Ø 总结
n 当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
n 栈非常适合于需要“就近匹配”的场合

3.1.4.3中缀表达式和后缀表达式

l 后缀表达式（由波兰科学家在20世纪50年代提出）
n 将运算符放在数字后面 ===》 符合计算机运算
n 我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯
l 实例
n 5 + 4 => 5 4 +
n 1 + 2 3 => 1 2 3 +
n 8 +( 3 – 1 ) 5 => 8 3 1 – 5 +
l 中缀转后缀算法：
遍历中缀表达式中的数字和符号：
n 对于数字：直接输出
n 对于符号：
u 左括号：进栈
u 运算符号：与栈顶符号进行优先级比较
Ø 若栈顶符号优先级低：此符号进栈
（默认栈顶若是左括号，左括号优先级最低）
Ø 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
l 右括号：将栈顶符号弹出并输出，直到匹配左括号,将左括号和右括号同时舍弃
遍历结束：将栈中的所有符号弹出并输出
l 动手练习
将我们喜欢的读的中缀表达式转换成计算机喜欢的后缀表达式
中缀表达式: 8 + ( 3 – 1 ) 5
后缀表达式: 8 3 1 – 5 +

3.1.4.4基于后缀表达式计算

l 思考
计算机是如何基于后缀表达式计算的？
例如：8 3 1 – 5 +
l 计算规则
遍历后缀表达式中的数字和符号
n 对于数字：进栈
n 对于符号：
u 从栈中弹出右操作数
u 从栈中弹出左操作数
u 根据符号进行运算
u 将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果
*

3.2队列(Queue)

3.2.1队列基本概念

队列是一种特殊的受限制的线性表。
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的t（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。如下图：

3.2.3队列的顺序存储

Ø 基本概念
采用顺序存储结构的队列称为顺序队列。

顺序队列存在假溢出现象，这种溢出并不是因为存储空间 不够而产生，而是因为顺序队列的存储单元没有重复使用机制。 解决的办法是将顺序队列设计成循环结构。
Ø 顺序循环队列
顺序循环队列把所有的存储单元构造成一个逻辑上首尾 相连的循环队列。

front = (front + 1)% length
rear = (rear + 1)% length

3.2.4队列的链式存储

Ø 基本概念
队列也是一种特殊的线性表；可以用线性表链式存储来模拟队列的链式存储。

4.树和二叉树

4.1树的基本概念

Ø 树的定义：
由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。
Ø 树的结构特点
n 非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
n 树的定义具有递归性，树中还有树。
n 树可以为空，即节点个数为0。
Ø 若干术语
n 根 à 即根结点(没有前驱)
n 叶子 à 即终端结点(没有后继)
n 森林 à 指m棵不相交的树的集合(例如删除A后的子树个数)
n 有序树 à 结点各子树从左至右有序，不能互换（左为第一）
n 无序树 à 结点各子树可互换位置。
n 双亲 à 即上层的那个结点(直接前驱) parent
n 孩子 à 即下层结点的子树 (直接后继) child
n 兄弟 à 同一双亲下的同层结点（孩子之间互称兄弟）sibling
n 堂兄弟 à 即双亲位于同一层的结点（但并非同一双亲）cousin
n 祖先 à 即从根到该结点所经分支的所有结点
n 子孙 à 即该结点下层子树中的任一结点
n 结点 à 即树的数据元素
n 结点的度 à 结点挂接的子树数（有几个直接后继就是几度）
n 结点的层次 à 从根到该结点的层数（根结点算第一层）
n 终端结点 à 即度为0的结点，即叶子
n 分支结点 à 除树根以外的结点（也称为内部结点）
n 树的度 à 所有结点度中的最大值（Max{各结点的度}）
n 树的深度(或高度) à 指所有结点中最大的层数（Max{各结点的层次}）
下图(c)中的结点数＝ 10，树的度＝ 3，树的深度＝ 3

4.2树的表示法

4.2.1图形表示法

事物之间的逻辑关系可以通过数的形式很直观的表示出来，如下图：

4.2.2广义表表示法

用广义表表示法表示上图：
中国（河北（保定，石家庄），广东（广州，东莞），山东（青岛，济南））
根作为由子树森林组成的表的名字写在表的左边。

4.2.3左孩子右兄弟表示法

左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树：


节点的结构：

节点有两个指针域，其中一个指针指向子节点，另一个指针指向其兄弟节点。

4.3二叉树概念

4.3.1二叉树基本概念

Ø 定义：
二叉树（binary tree）是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。
Ø 逻辑结构：
一对二（1：2）
Ø 基本特征:
n 每个结点最多只有两棵子树（不存在度大于2的结点）；
n 左子树和右子树次序不能颠倒（有序树）。
Ø 基本形态:

l 二叉树性质
n 性质1: 若根节点的层次为1，则二叉树第i层上至多有2个结点（i>0）
n 性质2: 在高度为k的二叉树中，最多有2-1个结点（k≥0）。
n 性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
l 概念解释：
² 满二叉树
一棵深度为k 且有2 -1个结点的二叉树。
特点：每层都“充满”了结点

² 完全二叉树
除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。


理解：k-1层与满二叉树完全相同，第k层结点尽力靠左
n 性质4: 具有n个结点的完全二叉树的深度必为ëlognû+1
(如 log2 (15) 点击 15 log / 2 log =)
n 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

使用此性质可以使用完全二叉树实现树的顺序存储。
如果不是完全二叉树咋整???
——— 将其转换成完全二叉树即可

缺点：①浪费空间；②插入、删除不便

4.3.2二叉树的表示

二叉树主要采用链式存储结构，顺序存储结构仅适用 于完全二叉树和满二叉树，还有静态链表。
Ø 二叉树的顺序存储结构

Ø 二叉树的链式存储结构
二叉树的链式存储结构主要有二叉链表和三叉链表两种。
n 二叉链表
二叉链表的节点结构如下：

n 结点数据类型定义：
type BinaryNode struct {
Ch byte

LChild BinaryNode
RChild BinaryNode
}
n 三叉链表表示法
三叉链表的的节点结构如下：


每个节点有三个指针域，其中两个分别指向子节点（左孩子，右孩子），还有一共指针指向该节点的父节点。
n 节点数据类型定义
type BinaryNode struct {
Ch byte
LChild BinaryNode
RChild BinaryNode
Parent *BinaryNode
}

4.3.3二叉树的遍历

Ø 遍历定义
指按某条搜索路线遍访每个结点且不重复（又称周游）。
Ø 遍历用途
它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
Ø 遍历方法
牢记一种约定，对每个结点的查看都是“先左后右” 。
限定先左后右，树的遍历有三种实现方案：
DLR LDR LRD
先 (根)序遍历 中 (根)序遍历 后(根)序遍历
n DLR — 先序遍历，即先根再左再右
n LDR — 中序遍历，即先左再根再右
n LRD — 后序遍历，即先左再右再根
注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。
从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

从虚线的出发点到终点的路径上，每个结点经过3次。
n 第1次经过时访问＝先序遍历
n 第2次经过时访问＝中序遍历
n 第3次经过时访问＝后序遍历

**

4.3.4二叉树编程实践

4.3.4.1 计算二叉树叶子节点数目

4.3.4.2 计算二叉树高度(深度)

思想：
l 求根结点左子树高度，根结点右子树高度，比较的子树最大高度，再+1。
l 若左子树还是树，重复步骤1；若右子树还是树，重复步骤1。

4.3.4.3 查找

4.3.4.4获得父母节点

4.3.4.5 拷贝二叉树

思想：
l malloc新结点，
l 拷贝左子树，拷贝右子树，让新结点连接左子树，右子树。
若左子树还是树，重复步骤1、2；若右子树还是树，重复步骤1、2。

4.4.4 二叉树的非递归遍历

二叉树三种遍历的递归算法可以通过设立一个栈用非递归 算法实现。以中根次序遍历为例，其非递归算法描述及栈变化 如下图所示。




首先将每个节点都设置一个标志，默认标志为假，根据节点的的状态进行如下流程。


执行上述流程，可以得到先序遍历的结果，如果想得到其他二叉树遍历结果，修改2.4步骤即可。

4.4.5 二叉树的层次遍历

二叉树的层次遍历过程及队列变化如下图所示。

4.4.6二叉树的应用：哈夫曼树 – 哈夫曼编码

1. 二叉树的路径长度：
从根结点到所有结点的路径长度之和称为该二叉树的 路径长度，即

完全二叉树的路径长度最短，反之不然。
2. 二叉树的外路径长度
从根结点到所有叶子结点的路径长度之和称为该二叉树 的外路径长度。一种编码方案的编码总长度为对应编码二叉 树的外路径长度，完全二叉树的外路径长度最短。
3. 二叉树的带权外路径长度
在字符使用概率各不相同的情况下，将字符的使用概率 作为二叉树中叶子结点的值，称为权。 从根到X结点的带权路径长度是X结点的权值与从根到X 结点路径长度的乘积。所有叶子结点的带权路径长度之和称 为二叉树的带权外路径长度，即

式中， wi为第i个叶子结点的权值， li为从根到第i个叶子结 点的路径长度。

4. 构造哈夫曼树并获得哈夫曼编码
哈夫曼树定义为带权外路径长度最短的二叉树。如给定n个叶子结点及其权值集合，则对应的哈夫曼树不唯一 。

构造哈夫曼树算法思路为：使权值越大的叶子结点越 靠近根结点，这样构造的二叉树，其带权外路径长度最小。

5. 哈夫曼编码的译码
利用哈夫曼树进行译码的过程：已知一个二进制位串S，从串S的第一位开始逐位地去匹配二叉树边上标记的0和 1， 由哈夫曼树的根结点出发，遇到0时向左，遇到1时向右，若 干连续的0和1确定一条从根到某个叶子结点的路径。一旦到达一个叶子结点，便译出一个字符。
【例】构造哈夫曼树并获得哈夫曼编码。
a) 采用静态链表存储哈夫曼树
静态链表的结点结构如下：

采用一维数组存储上述结点，对于有n个叶子结点的哈 夫曼树，数组长度为2n-1，前n个元素存储叶子结点，后n1个元素存储2度结点。设由权值集合{5,29,7,8,14,23,3,11}构 造一棵哈夫曼树，结点数组的初始状态和最终状态如下图 所示。

若权值集合{5,29,7,8,14,23,3,11}对应字符A～H，哈夫曼 树和哈夫曼编码如下图所示。

5.排序

5.1排序基本概念

现实生活中排序很重要，例如：淘宝按条件搜索的结果展示等。
l 概念
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。
l 排序数学定义：
假设含n个数据元素的序列为{ R1, R2, …, Rn}，其相应的关键字序列为{ K1, K2, …, Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：
Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn}的操作称作排序
l 排序的稳定性
如果在序列中有两个数据元素r[i]和r[j]，它们的关键字k[i] == k [j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在r[j]前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。



l 多关键字排序
排序时需要比较的关键字多余一个，排序结果首先按关键字1进行排序，当关键字1相同时按关键字2进行排序，当关键字n-1相同时按关键字n进行排序，对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可！
l 排序中的关键操作
n 比较：任意两个数据元素通过比较操作确定先后次序。
n 交换：数据元素之间需要交换才能得到预期结果。
l 内排序和外排序
n 内排序：在排序过程中，待排序的所有记录全部都放置在内存中，排序分为：内排序和外排序。
n 外排序：由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
l 排序的审判
n 时间性能：关键性能差异体现在比较和交换的数量
n 辅助存储空间：为完成排序操作需要的额外的存储空间，必要时可以“空间换时间”
n 算法的实现复杂性：过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能
l 总结
n 排序是数据元素从无序到有序的过程
n 排序具有稳定性，是选择排序算法的因素之一
n 比较和交换是排序的基本操作
n 多关键字排序与单关键字排序无本质区别
n 排序的时间性能是区分排序算法好坏的主要因素

5.2 交换排序

5.2.1冒泡排序

冒泡排序（bubble sort）的基本思想：比较相邻两个 元素的关键字值，如果反序，则交换。



Ø 冒泡总结：
n 冒泡排序是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。
n 上述例子总对冒泡做了优化，添加了flag作为标记，记录序列是否已经有序，减少循环次数。
n 冒泡排序算法的平均时间复杂度一般为O(n2 )，算法的空 间复杂度为O(1)。 冒泡排序算法是稳定的。

5.2.2快速排序

快速排序（quick sort）是一种分区交换排序算法，它的基本思想：在数据序列中选择一个值作为比较的基准值， 每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端， 介于两者之间的位置则成为基准值的最终位置。
1. 快速排序算法描述：

上述数据序列的快速排序（升序）过程如下图所示。

2. 快速排序算法分析
快速排序算法的平均时间复杂度为O(nlog2n)，算法的平均空间复杂度为O(log2n)。 快速排序算法不稳定。

5.3 选择排序

5.3.1直接选择排序

直接选择排序（straight select sort）的基本思想：第一趟从n个元素的数据序列中选出关键字最小（或最大）的元素并放到最前（或最后）位置，下一趟再从n-1个元素中选出最小（大）的元素并放到次前（后）位置，以此类推，经过n-1趟完成排序。
1. 直接选择排序算法描述

2. 直接选择排序算法分析
直接选择排序的比较次数为

直接选择排序算法的时间复杂度为O(n2 )，算法的空间复杂度为O(1)。 直接选择排序算法是不稳定的。

5.3.2堆排序

堆排序（heap sort）是完全二叉树的应用，它的基本思想：将数据序列“堆”成树状，每趟只遍历树中的一条路径。

5.4 插入排序

5.4.1直接插入排序

插入排序算法是一种简单的排序算法，也称为直接插入排序算法。它是一种稳定的排序算法，对局部有序的数据具有较高的效率。
插入排序算法是一个队少量元素进行排序的有效算法。比如，打牌是我们使用插入排序方法最多的日常生活例子。我们在摸牌时，一般会重复一下步骤。期初，我们手里没有牌，摸出第一张，随意放在左手上，以后每一次摸排，都会按照花色从小到大排列，直到所有的牌摸完。插入排序算法采用的类似思路，每一次从无序序列中拿出一个数据，将它放到已排序的序序列的正确位置，如此重复，直到所有的无序序列中的数据都找到了正确位置。

5.4.2希尔排序

希尔排序（shell sort）又称缩小增量排序，它的基本思想：分组的直接插入排序。
1、希尔排序算法描述：


2、希尔排序算法分析
希尔排序算法实际所需的时间取决于具体的增量序列， 所以它的时间复杂度分析比较复杂，一般为O(n(log2n)2 ) ，算法的空间复杂度为O(1)。 希尔排序算法不稳定。