数据结构相关知识
一.Java数据结构-线性表的设计与实现
相关知识
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。
顺序表是将表中的结点依次存放在计算机内存中，一组地址连续的存储单元中。
下图是一个顺序表示意图：
增加元素
现要插入元素到顺序表中，若没有指定添加元素的位置，则元素直接添加到数组末尾，表元素个数加1。
如指定要插入到位置index，则下标为index及之后的元素都需相应的移动。
现假设表中已有元素15 23 46 16 57 10 64，要插入一个新元素48到位置3（即调用list.Add(3,48)方法），因这里下标为3的元素是16，则16及之后的元素都需移动。
表中元素的变化过程如下图:
删除元素
同样，假设现在表中已有元素15 23 46 16 57 10 64，现要删除下标为3的元素，即调用list.remove(3)方法，则表中元素的变化过程如下图：
Java 数组
数组，是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来存储。你可以声明一个数组变量，如 arr[10] 来代替直接声明 10 个独立变量 arr0，arr1，....，arr9。
声明数组变量
首先必须声明数组变量，才能在程序中使用数组。下面是声明数组变量的语法：
Type[] arrVar; // 方式一Type arrVar[]; // 方式二这两种声明数组的方式都是正确的。 例如，声明一个double型数组，我们可以这样写：
double[] myArr或者double myArr[]创建数组
Java语言使用new操作符来创建数组，如下：
myArr = new Type[arrSize];arrSize是数组的大小，所以这里我们创建了一个大小为arrSize的Type类型的数组，并把它赋值给myArr。
数组变量的声明、创建数组可以用一条语句完成，如下：
Type[] arrVar = new Type[arrSize];Java 中的数组下标
在Java中，数组的下标是从0开始的。如一个有7个元素的数组，其下标范围是0，1，2，3，4，5，6。
我们实现的表中，下标仍然是从0开始，即list.get(0)返回的是第一个元素，list.get(n-1)返回的是第n个元素
链表
链表的概念
链式方式实现的表，简称链表。链表是使用指针（即引用）将存储元素的那些单元依次串联在一起。这种方法避免了数组中用连续的单元存储元素的缺点，因而在插入或者删除时不再需要移动元素来腾出空间或填补空缺。
链表中元素之间的逻辑关系（前还是后）是通过设置指针（引用）表示的。因此每个单元至少有两个域，一个用于数据元素的存储，一个用于指向其他单元的指针。这种具有一个数据域和多个指针域的存储单元称为结点。(node)。
结点图示：
单链表
单链表的每个结点只有一个指向表中下一个结点的指针。我们称最后一个结点为尾结点，尾结点的特征是指针域(next)引用为空(null)。
单链表的一个图示如下：
下图是一个带头结点的单链表：
头结点中的数据域不存放数据，指针域指向链表的第一个结点，便于对链表操作。
向单链表中添加元素
插入数据示意图：
从单链表中删除元素
删除元素示意图：
二.Java数据结构-循环链表的设计与实现
相关知识
单循环链表
循环链表是一种首尾相接的链表。其特点是无需增加存储量，只需对表的链接方式稍作改变，即可使得表操作更加方便灵活。
在单链表中，将末尾结点的指针域null改为指向表头结点或开始结点，就得到单链形式的循环链表，称为单循环链表。
为使空表和非空表的处理方式一致，循环链表中也可以设置一个头结点。这样空循环链表仅有一个自成循环的头结点。 如下图：
添加操作
单循环链表的添加操作与普通的单链表操作类似，只需添加时注意处理尾结点，使其指向头结点。下面是添加操作示意图。
这里采用的是尾插法，即在链表的末尾添加结点。我们使tail指向链表尾结点，因此添加结点node时只需改动tail和新结点node之间的链接关系即可。由于有头结点，所以空表和非空表的处理方式是一样的。
node.next=tail.next;tail.next=node;tail=node;遍历循环链表
在循环链表中，链表的尾结点不是指向null。因此要输出链表元素时，其终止条件就不再是像非循环链表那样判断p==null或p.next==null，而是判别它们是否等于某一指定结点，如头结点head。如下图所示：
单循环链表删除操作
单循环链表的删除操作与普通的单链表操作基本类似，通过遍历找到要删除结点的直接前驱，然后改变前驱的链接情况。如下图：
这里删除的是尾结点，由于我们在构建单循环链表时是用tail指向尾结点的，所以在删除尾结点后需改变tail的指向，如果删除的不是尾结点则不需改变tail指向。
双向循环链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表结点表示
双向链表中的结点由三个域组成，两个链接域一个数据域，如下图：
prev链接域指向结点的直接前驱，next链接域链接该结点的直接后继。
双向循环链表图示
下图是带头结点head的双向循环链表示意图：
双向循环链表添加操作
双向循环链表的添加操作示意图如下：
双向循环链表的删除操作
双向循环链表的删除操作示意图如下：
三.Java 数据结构之栈、队列
相关知识
栈
栈，是一种运算受限的线性表；仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。对栈的基本操作有push(入栈)和pop(出栈)，前者是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；后者是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
一个栈的示意图：
下面是1 2 3入栈出栈的示意图：
用数组表示线性表的相关知识可以参考之前的实训。
栈的数组表示
我们可以用一个数组S[1...n]来实现一个最多容纳n个元素的栈。该数组有一个top属性，指向最新插入的元素。栈中包含的元素为S[1...top]，其中S[1]是栈底元素，S[top]是栈顶元素。
下图是栈的数组实现的一个实例，top指向的是栈顶元素的下标：
(a)栈S内有4个元素。栈顶元素为9； (b)调用push(17)和push(3)后的栈S； (c)调用pop()并返回栈顶元素3的栈S。虽然3仍然在数组里，但它已经不在栈内了，此时栈顶的元素是17。
栈的链式存储
栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作只能在表头进行，如下图：
入栈
基于单链表实现的栈，入栈就是插入一个新结点，这里在头结点后插入新结点：
上图中，首先让新结点的next指向原来的栈顶元素head.next，保持对整个链表的引用，再把head.next指向新结点。
出栈
同样，出栈就是删除第一个结点：
删除头结点，可以直接把head.next指向head.next.next
队列
队列实现的是一种先进先出的策略，队列上的插入操作称为入队(enqueue)，删除操作称为出队(dequeue)。队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有队头(head)和队尾(tail)，当有新元素入队时，它被放到队尾的位置，就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在队头的那个，就像排在队伍前面等待最久的那个顾客一样。下图是一个队列的抽象模型：
队列的数组实现
对于一个队列数据结构，我们使用一个数组Q，以及队头head和队尾tail的位置来表示。head和tail代表队列的两端。下图表明利用数组Q[0...n]来实现一个最多容纳n+1个元素的队列的一种方式。该队列有一个属性Q.head指向队头元素。而属性Q.tail则指向下一个新元素将要插入的位置。队列中的元素存放在位置Q.head，Q.head+1，……，Q.tail-1。初始时有Q.head=Q.tail=0。
入队出队的操作应该是很清楚的。为使一个元素x入队，即执行enqueue(x)，让Q[tail]=x，然后使tail增1。若使元素出队（dequeue），我们返回Q[head]处的值，且使head增1。
循环队列
上述这种实现存在一个问题。以上图为例，经过12次入队操作后队列似乎满了，因为此时tail已经超过数组尾端了，再次执行入队操作会造成数组越界。然而，队列中也许只剩下几个元素。因为可能有若干元素出队了。像栈一样，即使有许多操作的情况下，队列也常常不是很大。 一个简单的解决方法是，只要head或tail到达数组尾端，它就绕回开头。我们称这种队列称为循环队列。
下图是一个队列实例。
这里我们利用数组Q[0...12]实现一个循环队列。
(a)队列包含5个元素，位于Q[6...10]；(b)依次调用Q.enqueue(17)，Q.enqueue(3)，Q.enqueue(5)后的队列；(c)调用Q.dequeue()方法并返回原队头值15后，队列的构成。此时新的队头是元素6。
链式队列
队列的链式存储结构简称为链式队列。它实际上是一个限制仅在表头删除和表尾插入的单链表。 链式队列的存储结构如下图所示：
其中front指向队头，tail指向队尾。出队操作在队头进行，入队操作在队尾进行。 ##### 出队操作
入队操作
四.Java 数据结构之二叉树
相关知识
树
定义
树(Tree)是n(n≥0)个结点的有限集合T，若n=0时称为空树，否则：
有且只有一个特殊的称为根
(root)结点;若
n>1时，其余的结点被分为m(m>0)个互不相交的子集T1，T2，T3...Tm，其中每个子集本身又是一棵树，称为根的子树。 这是树的递归定义，即用树来定义树。如下图所示：
树的基本术语
（1）结点的度 树中的一个结点拥有的子树数称为该结点的度。上图(b)中结点A的度是3,结点B的度是2，E的度是0。 （2）孩子和双亲 树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。同一个双亲的孩子称为兄弟。 上图(b)中结点B、C、D是结点A的子结点，而结点A是结点B、C、D的父结点。B、C、D的兄弟结点。 （3）叶子结点 树中度为0的结点称为叶子结点，相应地，度不为0的结点为非叶子结点。E、F、G、H、I、J是叶子结点。 （4）结点的层数和树的高度 结点的层数从根起算，根的层数为1，其余结点的层数等于其双亲结点的层数加1。树中结点的最大层数称为树的高度或深度。
二叉树
二叉树的定义
二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。这是二叉树的递归定义。
二叉树的五种基本形态
二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。 二叉树的五种基本形态如下图所示。
(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均非空的二叉树
满二叉树
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
二叉树的存储结构
顺序存储结构
用一组地址连续的存储单元依次自上而下，从左至右存储二叉树上的结点元素。 这种方式仅适用完全二叉树，对于非完全二叉树，将会造成空间浪费。
链式存储结构
以链式方式存储二叉树。用链接方式存储二叉树时，因二叉树的每个结点最多有两个孩子，所以每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为：
下图是二叉树的链式存储的一个实例图：
这里root指向二叉树的根结点，若二叉树为空，则root==null；若结点的某个孩子不存在，则相应的指针为null。
二叉树的遍历
所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
前序遍历
先序遍历是指遍历二叉树时，访问结点的操作发生在遍历其左右子树之前。 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，因此前序遍历的递归算法定义如下： 若二叉树非空，则： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。
上图的前序遍历结果为：3 4 0 5 7 6。
遍历次序示意图如下：
首先访问根结点3，接着遍历其左子树，访问结点4，继续遍历结点4的左子树，访问结点0，因结点0的左右子树均为空，结束对结点4的左子树的遍历，返回遍历4的右子树，遍历完4的右子树后，继续遍历根结点3的右子树，直至所有结点访问完为止。
二叉树的中序遍历
中序遍历二叉树时，对结点的访问次序为中序序列，即首先访问左子树，再访问根结点，最后访问右子树。 上图二叉树的中序遍历结果为：
0 4 5 3 6 7。
中序遍历次序示意图如下：
中序遍历的递归算法定义如下： 若二叉树非空，则： (1) 遍历左子树； (2) 访问根结点； (3) 遍历右子树。
二叉树的后序遍历
后序遍历是指在遍历二叉树时，先递归地打印结点的左子树、右子树，最后打印结点。对于下图：
其后序遍历结果为：0 5 4 6 7 3。
遍历示意图如下：
后序遍历的递归算法可表示如下： 若二叉树非空，则： (1) 遍历左子树； (2) 遍历右子树； (3) 访问根结点。
五.Java 数据结构之二叉搜索树
相关知识
六.Java 数据结构之图
相关知识
图是什么
图由顶点（Vertex）和边（Edge）组成。顶点代表对象。在画示意图的时候，我们使用点或圆圈来表示顶点。边表示的是两个对象的连接关系。在示意图中，我们使用连接顶点之间的线段来表示。顶点的集合是V、边的集合是E的图记为G=(V, E)，连接两点u和v的边用e=(u, v)表示。
图的种类
图大体上分为2种。边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。
我们可以给边赋予各种各样的属性。比较具有代表性的有权值（cost）。边上带有权值的图叫带权图。在不同问题中，权值可以代表距离、时间以及价格等不同的属性。如下图所示的带权图。
无向图的术语
对于无向图，如果两个顶点之间有边连接，那么就视为两个顶点相邻。相邻顶点的序列称为路径。起点和终点重合的路径叫做环。任意两点之间都有路径连接的图叫做连通图。顶点连接的边数叫做这个顶点的度。
没有环的连通图叫做树（tree），没有环的非连通图叫做森林。一棵树的边数恰好是顶点数减1。反之，边数等于顶点数减1的连通图就是一棵树。
有向图的术语
在有向图中，以顶点v为起点的边的数量称为v的出度，以v为终点的边的数量称为v的入度。
图的表示
为了能在程序中对图进行处理，需要用具体的数据结构存储顶点和边。在图的表示方法中，代表性的存储方法有邻接矩阵和邻接表。我们把顶点和边的集合记为V和E，|V|和|E|分别表示顶点和边的数量。
邻接矩阵
邻接矩阵使用大小为|V|×|V|的二维数组G来表示图。G[i][j]表示的是顶点i和顶点j的关系。
无向图中，只需知道“顶点i和顶点j之间是否有边连着”这样的信息，因此，如果顶点i和顶点j之间有边相连，那么G[i][j]和G[j][i]就设为1，否则设为0。
有向图中，只需知道“是否有从顶点i指向顶点j的边”这样的信息，因此，如果顶点i有一条指向顶点j的边，那么G[i][j]设为1，否则设为0。
有向图与无向图不同，并不满足G[i][j]=G[j][i]。
邻接表
邻接表，是通过把“从顶点1出发有到顶点2, 5的边”这样的信息保存在链表中来表示图的。即如果从顶点1到顶点2之间有边，则把顶点2添加到顶点1的邻接表中。具体请参考下图。
下面是两种表示的一个示例。
无向图的两种表示。(a)一个有5个顶点和7条边的无向图G。(b) G的邻接表表示。(c) G的邻接矩阵表示。
有向图的两种表示。(a)一个有6个顶点和8条边的有向图G。(b) G的邻接表表示。(c) G的邻接矩阵表示。
深度优先搜索介绍
图的深度优先搜索(Depth-First Search，DFS)，是找出图结构所有顶点的最简单最传统的方法。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程。
深度优先搜索图解
下面以无向图来对深度优先搜索进行图示。
对上面的图G进行深度优先搜索，从顶点A开始。
第1步：访问A。 第2步：访问(A的邻接点)C。 （在第1步访问A之后，接下来应该访问的是A的邻接点，即C, D, F中的一个。这里访问的是C） 第3步：访问(C的邻接点)B。 (在第2步访问C之后，接下来应该访问C的邻接点，即B和D中一个(A已经被访问过，就不算在内)。这里访问B。） 第4步：访问(C的邻接点)D。 (在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。) 第5步：访问(A的邻接点)F。 （前面已经访问了A，并且访问完了A的邻接点C的所有邻接点(包括递归的邻接点在内)；因此，此时返回到访问A的另一个邻接点F。 第6步：访问(F的邻接点)G。 第7步：访问(G的邻接点)E。
因此访问顺序是：A -> C -> B -> D -> F -> G -> E。
广度优先搜索介绍
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。
它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。
广度优先搜索图解
下面以"无向图"为例，来对广度优先搜索进行图示。
对上面的图G进行广度优先搜索，从顶点A开始。
第1步：访问A。 第2步：依次访问A的邻接点C，D，F。 （在第2步访问完C，D，F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。） 第3步：依次访问B，G。 （在第3步访问完B，G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。） 第4步：访问E。 因此访问顺序是：A -> C -> D -> F -> B -> G -> E。
Dijkstra算法
迪杰斯特拉算法（Dijkstra's algorithm）是由荷兰计算机科学家Edsger Wybe Dijkstra提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
在下图中找到从家到学校的最短路径：
(可以使用Dijkstra算法找到的最短路径是 Home->B->D->F->School)
基本思想：
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
算法步骤：
初始时，
S只包含源点，即S＝{v}，v的距离为0。T包含除v外的其他顶点，即:T={其余顶点}，若v与T中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。从
T中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。以
k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。重复步骤
2和3直到所有顶点都包含在S中。
伪代码：
function Dijkstra(Graph, source):
dist[source] := 0 // 源点到源点的距离为0
for each vertex v in Graph: // 初始化
if v ≠ source
dist[v] := infinity // 从源点到各个节点的距离初始化为无穷大
add v to Q // 把所有节点都加入队列Q中
while Q is not empty: // 主循环
v := vertex in Q with min dist[v] // 第一次循环，返回的必然是源点
remove v from Q
for each neighbor u of v: // 遍历v的所有邻接节点
alt := dist[v] + length(v, u)
if alt < dist[u]: // 找到了到u的更短的路径
dist[u] := alt // 更新到u的距离
return dist[]
end function七.Java 数据结构之排序
相关知识
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
上图是一个从小到大排序的选择排序过程。第一次，我们从初始序列中找出了最小的元素
11，把它放到第一位；第二次我们从剩下的元素中找出最小的元素13，把它放到第二位，以此类推，直到所有元素从小到大排好序。
插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
假设我们输入的是5，1，4，2，3，我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了1，5，4，2，3。
接下来我们看第三个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了1，4，5，2，3我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。
再来看第四个数字，这个数字是2，我们将2和它左边的数字相比，都比2大，所以就将2一路往左移动，一直移到2的左边是1，这时候排序变成了1，2，4，5，3。
最后，我们检查第五个数字，这个数字是3，3必须往左移，一直移到3的左边是2为止，所以我们的排列就变成了1，2，3，4，5，排序完成。
归并排序
归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法。归并是指将若干个已排序的子序列合并成一个有序的序列。若将两个有序序列合并成一个有序序列，称为二路归并。
原理
假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直到得到一个长度为n的有序序列为止。
上图是一个二路归并排序过程示例，经过三次归并操作后完成了排序。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序
快速排序的基本思想是： 1．先从数列中取出一个数作为基准数。 2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。
现在假设我们对6 1 2 7 9 3 4 5 10 8这10个数进行排序。首先在这个序列中找一个数作为基准数。为了方便，取第一个数6作为基准数。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列： 3 1 2 5 4 6 9 7 10 8 具体过程是：从右往左找比6小的数，从左往右找6大的数，然后把这两个数交换，如下图所示， 最后得到
3 1 2 5 4 6 9 7 10 8。
我们接着在对6的左右区间分别进行同样的操作。会得到类似1 2 3 5 4和8 7 9 10的排列。直到区间只有一个数，处理结束。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
堆
堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 当一个含有n个元素的数组{k1, k2... ki...kn},当且仅当满足下列关系时称之为堆： (ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4... n/2)
即，如果用堆中的元素依次从上至下，从左至右构建一棵完全二叉树，那么这棵二叉树的任意节点的值都大于其子节点的值(或都小于其子结点的值)，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质
通常堆是通过一维数组来实现的。在索引起始位置为1的情形中： 父节点i的左子节点在位置 (2i); 父节点i的右子节点在位置 (2i+1);
大根堆堆顶元素最大
堆排序
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得选取最大（或最小）关键字变得简单。
用大根堆排序的基本思想
先将初始数组
R[1..n]构造成一个大根堆，此堆为初始的无序区。再将关键字最大的记录
R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key由于交换后新的根
R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
大根堆排序算法的基本操作
建堆，建堆是不断调整堆的过程，从
len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点
i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交换节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面
len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。
八.java数据结构之二分搜索
相关知识
折半查找（二分查找）
二分查找又称为折半查找，是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程：
从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较；
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
搜索过程如下图，例如查找9在数组中第一次出现的位置：
详细步骤：
给予一个包含n个带值元素的数组A：A[0] ≤ ··· ≤ A[n-1]，以及目标值T，进行折半查找过程如下：
让初始位置（
L）为0，结束位置（R）为n-1；如果
L > R，则查找失败；令
m（中间元素），为[L+R/2]；如果
A[m] < T，令L为m + 1并回到步骤二；如果
A[m] > T，令R为m - 1并回到步骤二；如果
A[m] = T，搜索结束，返回值m。
这个迭代步骤会持续透过两个变量追踪搜索的边界。
注意： 二分查找是针对的排好序的数组。
复杂度分析
时间复杂度
折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn)。（n代表集合中元素的个数）
空间复杂度
O(1)