算法与数据结构开篇

你真的会数据结构吗？

公司开发一个客服电话系统，小菜需要完成客户排队模块的开发，经过三次修改：

第一次：小菜使用了数据库设计了一张客户排队表，并且设置了一个自动增长的整型id字段，来一个用户，就在这张表的末尾插入一条数据，等客服系统一空闲，就将表中最前的的客户提交，然后删除这条记录。

• 实时排队模块，在内存中实现即可，无序用数据库

第二次：小菜用数组变量重新实现了这个功能，害怕数组不够大，选择远大于实际情况的100作为数组长度

• 数组虽然可以满足一定需求，但是需要考虑溢出问题，以及新增和删除后的数据移动，显然不是很方便

第三次：小菜使用了数据结构中的 “队列结构” 终于满足了需求

说明：此例子归纳参考自《大话数据结构》

为什么你的程序比别人的慢？(算法问题)

来看一个问题：

公元前五世纪，我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？请设计一个“高效”的算法求解。

也就是说：

买一只公鸡要五文，买一只母鸡要三文，而一文可以买三只小鸡，共有100文，问公鸡母鸡小鸡各能买几只？

话不多说，我们先给出一种最容易想到的方式，也就是列两个三元方程组

也就是满足鸡的总数为100，同时花钱数也为100，我们来看一下代码实现

方式一：

//i j k 分别代表公鸡 母鸡 雏鸡的数量 
//20、34、300 为100元最多能买公鸡、母鸡、小鸡的数量
for (int i = 0; i < 20; i++) {
	for (int j = 0; j < 34; j++) {
		for (int k = 0; k < 300; k = k + 3) { //k = k + 3 是为了满足小鸡实际存在的要求
			if (5*i + 3*j +  k/3 == 100 && i + j + k == 100) {
				cout << "公鸡 母鸡 雏鸡 数量分别为：" << i <<", "<< j <<", "<< k << endl;
			}
		}
	}
}

我们用了三层循环，有没有办法能简化以下代码呢？能不能减少循环层数呢？这显然是可行的，上面小鸡的数量这一层明显可以省略的，因为总数是已知的

方式二：

for (int i = 0; i < 20; i++) {
	for (int j = 0; j < 34; j++) {
			
		k_temp = 100 - i - j;
			
		if (k_temp % 3 == 0)
			k = k_temp;
		
		if (5*i + 3*j +  k/3 == 100 && i + j + k == 100) {
			cout << "公鸡 母鸡 雏鸡 数量分别为：" << i <<", "<< j <<", "<< k << endl;
		}
	}
}

确实程序更加优化了一些，但是这样是不是就可以了呢？其实还可以优化为一层循环！

方式三：

int i, j, k, t;
for (int t = 0; t <= 25/7; t++) {
	i = 4 * t;
	j = 25 - 7 * t;
	k = 75 + 3 * t;
	cout << "公鸡 母鸡 雏鸡 数量分别为：" << i <<", "<< j <<", "<< k << endl; 
} 

上例中对程序的优化涉及到了数学的运算

//根据花钱的总数为100列式
5x + 3y + (100 - x - y)/3 = 100

//对上式进行化简
y = 25 -(7/4)x
  = 25 - 2x + x/4
    
//设 x/4 = t，原式子可变为
y = 25 - 7t
    
//可以得到三个不等式
x = 4t >= 0
y = 25 - 7t >= 0
z = 75 + 3t >= 0

//解得
t >= 0
t <= 25/7

为了增加说服力，我们测试每一个程序的运算时间，不太熟悉的朋友我下面已经贴出了代码

#include<ctime>
clock_t startTime,endTime;
startTime = clock();

......测试代码

endTime = clock();
cout << "The run time is: " << (double) (endTime - startTime) / CLOCKS_PER_SEC << "s" << endl; 

我们将数据放大一些，方便体现差异，我们将总金额和总数量均改为1000 下面是三种方式的运算时间

The run time is: 0.114s
The run time is: 0.03s
The run time is: 0.026s

很显然程序逐步的到了优化，减少了for循环 大大的减少了循环次数，所以节省了时间

##为什么要一起学习数据结构和算法？

想要回答这个问题，我们先开看一下数据结构和算法的概念

数据结构概念

数据结构是指相互之间存在一种或多种特定关系数据元素的集合

也就是说，计算机在对数据进行存储的时候并不是杂乱无序的而是拥有一定规则的，一个或多个数据元素之间拥有一定的相互关系，所以也可以说数据结构是计算机存储和组织数据的方式

算法的概念

算法是一种可以被计算机使用来解决问题的的方法，这种方法也正是解决问题的具体步骤

对于小型的程序而言，即使这个算法比较差劲，解决问题的步骤比较累赘繁琐，也不会有很大的关系，只要能解决问题的就是好程序，但是如果对于数据量较大的中大型程序，我们就需要对方法的时间和空间进行有效的利用，也就是设计一个高效的算法，在同样硬件设备的情况下，有时候甚至可以将速度提高十倍甚至百倍

程序 = 数据结构 + 算法

数据结构是对计算机所存储的数据之间的一种组织管理，算法是对数据进行操作从而将你解决问题的方法在计算机中具体实现，也就是说，在计算机中而言，其实这两者单独拿出来讨论是没有什么实际意义的，就像鱼离不开水一样，即使一个优秀的算法，如果数据之间没有任何结构关系可言，算法也就无从实现，也就没有意义了，而即使数据之间有了组织关系，但是不对其进行操作这显然也没有意义。

简单总结：只有数据结构的程序是没有灵魂的，只有算法的程序却只有魂魄，没有躯体

不可否认，数据结构是非常重要的，但我更加倾向于算法为核心，正如 Algorithms(4th.Edition) 中的观点，数据结构是算法的副产品或者结果，在我看来，如何建立一个有效且高效的算法以及模型是更重要一些的，开发的最终目的就是通过程序利用科技设备实现我们实际生活中的一些需求，我们遇到问题的第一步都是在现实中对问题进行分析，然后设计出合适的方法，然后就要想办法将这种方法表达给计算机设备，但是这个时候就需要数据结构这样一种满足需要的产物，来支持我们对我们的设备具体表达我们的方法，尤其随着数据量的检验，不同的算法就会对解决实际问题的效率产生更大的影响，我用一个不是很恰当却很形象的例子表达就是：你的身体（数据结构）死了，你可能还活着，但你的灵魂（算法）死了，你即使活着也已经死了

当然数据结构的重要性也是不容置疑的，一个好的数据结构，可以帮助我们的程序更加高效，如果什么时候，模型以及算法的选用已经可以根据数据的特点以及需求选用，我们就可以将更多的精力投入到数据结构的设计中去，不过这也仅仅是一种美好的假想，所以我们还是要学好算法，但是学好算法，我们也就要对支持我们算法的数据结构进行一定的研究

说了一些个人的观点，那让我们赶紧介绍一些入门的必备知识

数据结构的基本概念和术语

• 数据：描述客观事物的数字和符号，是能够被计算机识别且进行处理的的符号集合

  • 整型和实数型数据是可以直接进行数值计算的

  • 文字、图像、图形、声音、视频等多媒体信息则可以通过合适的编码保存处理

    例如：文本通过字符编码处理、声音通过储存波形 (WAV) 或在波形分解后存储其振幅特性然后压缩 (MP3)

• 数据元素：组成数据且有意义的的基本单位 (个体)

  • 例如：猫和狗都是动物群体中的一个数据元素

• 数据项：组成数据元素具有特定意义的最小不可分割单位

• 作为人这个类群中具体的个体，一个人而言，其所拥有的手、脚、眼、鼻，亦或者姓名、年龄、身高、等都属于数据项

• 数据对象：性质相同的数据元素的集合，是数据的子集

  • 例如：人类中一些人的生日、身高相同

逻辑结构和物理结构(存储结构)

逻辑结构

逻辑结构：数据对象中数据元素之间的相互关系

① 集合结构：数据元素之间的唯一关系就是属于同一个集合

② 线性结构：数据元素之间存在一对一的关系（除首尾元素均存在前驱和后继）

③ 树形结构：数据元素之间存在一对多的关系

④ 图形结构：数据元素之间存在多对多的关系

• （每一个数据元素看做一个节点，元素之间的逻辑关系用连线表示，如果关系有方向则连线带箭头）

物理结构(存储结构)

物理结构：数据的逻辑结构关系在计算机中的存储形式

① 顺序存储结构：把元素分别放在地址连续的存储单元中的存储方式

• 也就是说：元素一个一个有序的排好队，各自占据一定的空间，例如定义一个含有6个浮点型数据的数组：然后内存中的一块大小为6个浮点型数据大小空间就会被计算机所开辟，然后数据存入时，依次顺序摆入

② 链式存储结构：把元素存储在任意的存储单元中的存储方式

• 因为数据元素位置不确定，所以需要通过指针指向到元素的存储地址，从而确定不同数据元素之间的位置

• 举例：200人同时在一个阶梯教室上课，同学们坐的位置是没有关系的，老师点名签到的时候，你只需要关注你学号前一位的同学有没有被点到，点到后，你就知道下一个该你了

③ 散列 (哈希) 存储方式：是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术

• 你别慌，我这就来解释了，它的原理就是，将一个节点的关键字key作为自变量，通过一个确定的函数运算f(key)，其函数值作为节点的存储地址，将节点存入到指定的位置上，查找的时候，被搜索的关键字会再次通过f(key)函数计算地址，然后读取对应数据

• 我们后面会专篇讲解这个内容，现在做一个简单的了解即可

④ 索引存储方式：存储时，除了存储节点，还附加建立了索引表来表示节点的地址

算法的特征

• 输入：算法具有零个或者多个输入（零个的情况例如打印输出字符串，或者算法自身已经给定了初始条件）

• 输出：算法具有一个或者多个输出，用来反映算法对输入数据加工后的结果

• 有穷性：算法必须在执行有限个步骤后终止

  • “有限” 的定义不是绝对的，而是实际应用中合理的可接受的

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

  • 也就是说，唯一的输入只有唯一的输出

• 可行性：算法的每一步都是可行的，通过有限步骤可以实现

算法的设计要求

• 正确性：合理的数据输入下，最终可以输出能解决问题需求的正确答案

  • 对正确的理解：
    • 无语法错误
    • 输入合法和非法的数据均可以得到正确答案
    • 输入刁难的数据依旧可以输出满足需要的答案

• 可读性：算法便于阅读和理解

  • 算法应该层次分明，易读易懂，方便二次调试和修改

  • 复杂一些的算法，变量的命名尽量恰当一些，用阿里的开发手册中的一句话就是说：“正确的英文拼写和语法可以让阅读者易与理解避免歧义”，“为了达到代码自解释的目标，任何自定义编程元素在命名时，使用尽量完整的单词组合来表达其意”

• 健壮性：当数据不合理的时候，算法也能对各种情况作出处理，而不是报出异常，或者输出错误的答案

• 高效性：尽量满足时间效率高，存储率低的需求

函数的渐进增长

次数	算法A ：2n + 4	算法B ：3n + 3	算法C ：2n	算法D ：3n
n = 1	6	6	2	3
n = 2	8	9	4	6
n = 3	10	12	6	9
n = 10	24	33	20	30
n = 100	204	303	200	300

n = 1的时候 算法 A 和 B 的效率一致，但是从n = 2的时候开始算法 A 的效率已经大于算法 B 了，n值变大后，算法 A 相比 B 变的更加快速

• -所以在n值没有限定的情况下，只要在超过某数值N后，函数值就一直大于另一个函数，那么我们称函数是渐进增长的

  函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的渐近增长快于g(n)

• 接着我们分别用 AC 、BD进行对照，你会发现其实后面的加数对算法的影响几乎是忽略不计的，所以我们一般选择忽略这些加法常数

次数	算法A ：2n + 6	算法B ：3n² + 3	算法C ：n	算法D ：n²
n = 1	8	6	1	1
n = 2	10	15	2	4
n = 3	12	30	3	9
n = 10	26	303	10	100
n = 100	206	30003	100	10000

算法 A 和 B 比较的时候，n = 1的时候 B效率更高，从n = 2开始 算法 A 就比较高效，随着数据的输入，体现的越明显，但是我们同时将这两个算法去掉最高次项的系数，接着可以看到对数据的走向仍然影响不大

• 最高次项的系数对数据走向的影响不大

• 最高项的指数大的函数，随着n的增长，结果也会快速增长

• 判断算法效率的时候，应主要关注最高次项，其他次要项或者常数项常常可以忽略

算法的时间复杂度

算法的时间复杂度是一个函数 T(n)，它定性描述该算法的运行时间，通常用大O表示法，记作：T(n) = O(f(n)) 例如3n² + 2n + 1 的时间复杂度为 O(n²)

注意：

• T(n) = O(f(n)) 解释：随着n增大算法执行时间的增长率和f(n)的增长率相同，同时也考察输入值大小趋于无穷的情况，也称作算法的渐进时间复杂度

• 在这个过程中，不考虑函数的低阶项、常数项和最高项系数，

常见的时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)

实际开发中，我们常见到的还是前几个加粗的

我们还需要提到两个概念：

最坏情况与平均情况

最坏情况就是，运行时间的最大值，情况不能再坏了

平均时间就是

一般情况下，我们都是指最坏时间复杂度，但平均时间是最有意义的时间，因为它与我们的期望值更接近

作者的话

这些文章，当然谈不上算什么有深度的技术，但是我在尽可能的将一些概念通过举例、图表等方式给对这方面知识有需要的朋友，快速的入门，通过一些通俗的说法，先对一些知识有一定的了解，在此基础上，去看一些深入的权威书籍，或者大牛的博文，就会不至于劝退，自知技术有限，但仍然想给一些刚刚接触这部分知识的朋友们一些帮助，总得一个人，经历一些难捱的日子，你才会变得更加强大！

结尾：

如果文章中有什么不足，或者错误的地方，欢迎大家留言分享想法，感谢朋友们的支持！

如果能帮到你的话，那就来关注我吧！如果您更喜欢微信文章的阅读方式，可以关注我的公众号

在这里的我们素不相识，却都在为了自己的梦而努力 ❤

一个坚持推送原创Java技术的公众号：理想二旬不止

码字不易，喜欢请点赞！！！
1.数据结构基础
2.线性表(顺序存储、链式存储)

• 元素之间是有顺序的：第一个元素无前驱，最后一个元素无后继，其他元素都有前驱和后继
• 顺序存储结构：用一段地址连续的存储单元一次存储线性表的数据元素(存取时间复杂度为O(1)，插入或删除时间复杂度为O(N)，适合数据量不大并且存取操作多的数据)
• 优缺点：
  
• 链式结构：元素信息+后继元素的地址(读取、插入、删除：时间复杂度O(N))
• 头指针：链表第一个结点的存储位置；
• 尾结点：后继不存在，即最后一个结点的指针为空；
• 头结点：第一个结点前设一个结点，可以不存储任何信息，也可以存储长度等附加信息
  
• 优缺点：
  

3.栈

4.队列、循环队列

5.串

• 子串查找：KMP算法

6.树

• 节点的度：节点的分支数目

• 树的度：树内各个节点的度的最大值

• 叶节点、终端节点：度为0的点

• 树的深度：树中节点的最大层次
  

• 二叉树：n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两颗互不相交、分别称为根节点的左子树和右子树的二叉树组成。

• 二叉树的5种形态：
  

• 满二叉树：
  

• 完全二叉树
  

• 二叉树的性质

• 二叉树的第i层，最多有$2^{i-1}$结点

• 深度为k的二叉树，最多有$2^k-1$个节点

• 具有n个结点的完全二叉树的深度为$[lo{g}_2^n]+1$（[x]表示对x下取整）

• 二叉树T，叶子节点数为$n_0$，度为2的节点数为$n_2$，则$n_0$ = $n_2$ + 1
  因为节点数n = $n_0$ + $n_1$ + $n_2$ = 2$n_2$ + $n_1$ + 1
  所以：$n_0$ = $n_2$ + 1
  

• 对于完全二叉树的节点i：
  

• 二叉树的存储

• 一维数组存储：使用一维数组按照顺序存储，对于不存在的节点使用空来占位

• 二叉链表：lchild+data+rchild形式
  

• 二叉树的遍历：前序遍历、中序遍历、后序遍历、层序遍历(逐层遍历)

• 已知前序和中序，可以确定一颗二叉树

• 已知后序和中序，可以确定一颗二叉树

• 已知前序和后序，不可以确定一颗二叉树

• 树、森林、二叉树的转换

• 树转换成二叉树

1.加线：兄弟节点之间加一条线
2.去线：对每个节点只保留第一个子节点的连线，删除其他子节点的连线
3.层次调整：第一个子节点为左孩子，兄弟节点转成第一个子节点的右孩子

eg：

• 森林转成二叉树

#森林由多棵树组成，将森林中每一颗树都视为兄弟，按照兄弟的办法来处理
1.将每棵树转成二叉树
2.将后面的树的根节点作为前面的树的根节点的右孩子

eg：

• 二叉树转成树

#树转成二叉树的逆过程
1.加线：左孩子的所有右孩子，与左孩子的父节点连接起来。
2.去线：删除原二叉树中的所有右孩子连线。
3.层次调整：旋转

eg：

• 二叉树转成森林

#如果根节点有右孩子，则是森林，没有孩子，则是一棵树
1.先将根节点的右孩子线删除，拆成多颗二叉树
2.然后对每个二叉树执行拆分成树的操作

eg：

• 树与森林的遍历

• 树的遍历：先根遍历、后根遍历
  
  

• 森林的遍历：前序遍历、后续遍历
  
  前序遍历结果：ABCDEFGHJI
  后序遍历结果：BCDAFEJHIG
  

• 哈夫曼树

• 简介
  

1.节点的带权路径：节点到根之间的路径长度与节点权值的乘积
2.树的带权路径：树中所有节点的带权路径之和
3.哈夫曼树：带权路径长度WPL最小的二叉树，称为哈夫曼树，也叫最优二叉树

二叉树a的WPL=51+152+403+304+104=315
二叉树b的WPL=53+153+402+302+102=220
这个结果意味着，如果有10000个学生需要计算，那么二叉树a的判断方法需要计算31500次，而二叉树b的方法需要计算22000次。

• 哈夫曼树构造
  
  
  

7.图

• 定义
  

• 无向边：顶点之间没有方向，称这条边为无向边，用无序偶对$(v_i,v_j)$来表示

• 有向边：顶点之间有方向，称这条边为有向边，也称为弧，用有序偶对$<v_i,v_j>$来表示，如果图中任意两个顶点的边都是有向边，则称该图为有向图，要区分开弧尾$v_j$和弧头$v_i$

• 无向图:如果任意两个顶点之间都存在边，则称该图为无向完全图，含有n个顶点的无向完全图有$n(n-1)/2$条边。

• 有向图:如果任意两个顶点间都存在方向互为相反的两条弧，则称为有向完全图。含有n个顶点的有向完全图有$n(n-1)$条边。

• 连通图：无向图中，如果两个顶点之间有路径，说明两顶点是连通的，如果对于图中任意两个顶点都是连通的，则称该无向图是连通图。

• 极大连通子图称为连通分量：需要是1.子图；2.子图是连通的；3.连通子图含有极大顶点数；4.具有极大顶点数的连通子图包含依附这些顶点的所有边。

• 度：无向图顶点的边数叫度，有向图的顶点分为出度和入度。

• 生成树、森林：无向图中连通且n个顶点有n-1条边叫生成树；有向图中一个顶点入度为0，其余顶点入度为1称为有向树；一个有向图由若干个有向树构成生成森林。

• 图的存储结构
  由于图的结构比较复杂，任意两点之间都可能存在联系，因此不能用简单的顺序存储结构来表示。

• 邻接矩阵

邻接矩阵的存储方式：两个数组来表示图;
一个一维数组存储图中顶点的信息;
一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

• 邻接表

临近矩阵的问题：对边数相对顶点数较少的图，这种结构是对存储空间的极大浪费，太稀疏。

邻接表：将数组与链表结合起来

无向图：

有向图：

带权有向图：

• 十字链表

在有向图中，邻接表是有缺陷的，关心了出度问题，要想知道入度，就必须遍历整个图；
反之逆邻接表解决了入度却不能解决出度；
那能否将邻接表与逆邻接表结合起来呢？
答案是肯定的，于是就有了一种新的有向图的存储方法：十字链表法。

• 邻接多重表

• 边集数组
  边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素有一条边的起点下标(begin)、终点下标(end)和权(weight)组成。
  

• 图的遍历：深度优先搜索、广度优先搜素

• 深度优先搜索：

• 广度优先遍历：类似于树的层序遍历

• 深度优先更适合目标比较明确，以找到目标为主的情况，广度优先更适合在不断扩大遍历访问时找到最优解的情况。

• 最小生成树

• 定义：给定一个无向图，如果他的某个子图中，任意两个顶点都能互相连通并且是一棵树，那么这棵树就叫做生成树，如果边上有权值，那么使得边权和最小的生成树叫做最小生成树。即构成连通网的最小代价生成树称为最小生成树。

• 实际问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？

• 普里姆算法—Prim算法：适合稠密图
  【算法思想】：Prime算法是一种贪心算法，它最初将无向连通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好连接入生成树的点，否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u，其余的点属于VB，每次添加一个VB中的点到VA，该点是集合VB到集合VA中距离最小的一个点。直到V个顶点全部属于VA，算法结束。显然出发点不同，最小生成树的形态就不同，但边权和的最小值是唯一的。
  eg:
  下面我们对下面这幅图求其最小生成树：
  
  假设我们从顶点v1开始，所以我们可以发现（v1,v3）边的权重最小，所以第一个输出的边就是：v1—v3=1:
  
  然后，我们要从v1和v3作为起点的边中寻找权重最小的边，首先了（v1,v3）已经访问过了，所以我们从其他边中寻找，发现(v3,v6)这条边最小，所以输出边就是：v3—-v6=4
  
  然后，我们要从v1、v3、v6这三个点相关联的边中寻找一条权重最小的边，我们可以发现边(v6,v4)权重最小，所以输出边就是：v6—-v4=2.
  
  然后，我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最小的边，发现边（v3，v2）的权重最小，所以输出边：v3—–v2=5
  
  然后，我们就从v1、v3、v6、v4，v2这2五个顶点相关联的边中寻找权重最小的边，发现边（v2，v5）的权重最小，所以输出边：v2—–v5=3
  
  最后，我们发现六个点都已经加入到集合U了，我们的最小生成树建立完成。
  【算法步骤】
  选定图中的任意一个顶点v0，从v0开始生成最小生成树。
  （1）初始化dist[v0]=0，其他点的距离值dist[i]=∞。其中dist[i]表示集合VB中的点到VA中的点的距离值。
  （2）经过N次如下步骤操作，最后得到一棵含N个顶点，N-1条边的最小生成树：
  ①选择一个未标记的点k，并且dist[k]的值是最小的
  ②标记点k进入集合VA
  ③以k为中间点，修改未标记点j，即VB中的点到VA的距离值
  （3）得到最小生成树T。

• 克鲁斯卡算法—Kruskal算法：适合稀疏图
  【算法思想】：Kruskal算法也是一种贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
  【算法步骤】：
  （1）将G中的边按权值从小到大快排。
  （2）按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边，否则标记当前边并计数。
  （3）重复（2）的操作，直到生成树T中包含n-1条边，否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。
  【算法实现】：Kruskal算法
  算法的关键在于如何判定新加入的边会不会使图G’产生环，在这里用并查集，如果新加入的边的两个端点在并查集的同一集合中，说明存在环，需要舍弃这条边，否则保留当前边，并合涉及的两个集合。

• 最短路径

• 迪杰斯特拉算法(Dijkstra)：单源最短路径
  【算法思想】：首先将图中的顶点分成两组，第一组S中包括已经确定最短路径的顶点（初始情况包含源点）;第二组V-S中包括还未确定最短路径的顶点。然后按照路径长度递增的顺序计算源点到各顶点的最短路径，逐个将第二组中的数据加入到第一组中，直到S = V。
  
  【算法实现】：Dijkstra
  【动态演示】
  

• 弗洛伊德算法(Floyd)：任意两个点对最短路径
  【算法思想】：用简单的语言来解释，就是对于点Vi到Vj的距离，如果存在点Vk，使得点Vi到点Vk的距离加上点Vj到点Vk的距离之和小于点Vi到Vj的距离，那么就用点Vi到点Vk的距离加上点Vj到点Vk的距离之和去替代点Vi到Vj的距离。
  【算法实现】：Floyd
  【结果展示】
  

8.查找和排序算法

• 顺序查找
• 二分查找(折半查找)
• Hash查找
• 二叉排序树：左子树小于根节点，右子树大于根节点
• 冒泡排序
• 短冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序：大根堆(每个节点的值都大于其左右子节点的值)；小根堆(每个节点的值都小于其左右子节点的值)
  

参考链接：
https://blog.csdn.net/Asher117/article/details/89306091
https://blog.csdn.net/Asher117/article/details/89351068
https://blog.csdn.net/Asher117/article/details/93647879
https://mp.weixin.qq.com/s/GjqKMEwLHq16FaXdoHy8xA
https://blog.csdn.net/jiaoyangwm/article/details/80808235
https://blog.csdn.net/dengpei187/article/details/51899550
https://mp.weixin.qq.com/s/Oyk7_vR3KtIBXf5AnhmWNQ
https://blog.csdn.net/qq_39826163/article/details/81660819
https://mp.weixin.qq.com/s/LCs2wmfCGw9oc3d1hkJn2w
https://mp.weixin.qq.com/s/Iul7pHHiAsun80Dad9jqkw
https://blog.csdn.net/qq_38499859/article/details/79122634
https://blog.csdn.net/Asher117/article/details/89500637

本文是王争老师的《算法与数据结构之美》的学习笔记，详细内容请看王争的专栏 。有不懂的地方指出来，我做修改。

数据结构与算法思维导图

数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。
数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

最常用的数据结构预算法:

• 数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
• 算法： 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

1  算法的复杂度

1.1大O复杂度表示法

 公式:

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式， 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

      所以，第一个例子中的T(n) = O(2n+2)，第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

      当n很大时，你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。
 

1.2.复杂度分析法则

1）单段代码看高频：比如循环。
2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
3）嵌套代码求乘积：比如递归、多重循环等
4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

1.3 时间复杂度分析

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1.4 几种常见时间复杂度实例分析

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
O(2^n)（指数阶）、O(n!)（阶乘阶）

• O(1) :

常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

• O(logn)、O(nlogn)

i=1;
while(i<=n) {
    i = i*2;
}

x=log2n，所以，这段代码的时间复杂度就是 O(log2n)

• O(m+n)、O(m*n)

   int cal(int m, int n) {
      int sum_1=0;
      int i=1;
      for(;i<m;++i){
         sum_1 = sum_1 + i;
      }
      int sum_2 = 0;
      int j=1;
      for (;j<n;++j){
         sum_2 = sum_2 + j;
      }
      return sum_1 + sum_2;
   }

从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复 杂度就是0(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

1.5 空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
    inti=0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] =i* i;
    }
    for(i=n-1;i>=0;--i){
        print out a[i]
    }
}

跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i,但是它是常最阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。

我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。

1.6 复杂度增长趋势图:

最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

一、复杂度分析的4个概念
1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念？
1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度？
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

1、数组

线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构：数组，链表、队列、栈等。

什么是数组:

1.  数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
2.  连续的内存空间和相同类型的数据(随机访问的前提)。
3. 优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。
4. 对内存空间要求高，需要一块连续的内存空间。

• 数组怎么根据下标随机访问的？

通过寻址公式：a[i]_address = base_address + i * data_type_size
其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

为何数组插入和删除低效：

插入：
若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。
最好情况时间复杂度 O(1)

如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。

最坏情况复杂度为O(n)

平均负责度为O(n)

2. 低效的插入和删除
1） 插入：从最好O(1) 最坏O(n) 平均O(n)
2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。
3） 删除：从最好O(1) 最坏O(n) 平均O(n)
4） 多次删除集中在一起，提高删除效率
记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

2、链表

• 什么是链表

1.和数组一样，链表也是一种线性表。
2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
3.链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

• 链表的特点

1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。

2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

• 常用链表

1.单链表

1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

2.循环链表

1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2）适用于存储有循环特点的数据，比如约瑟夫问题。

3.双向链表

1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3）性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表：

首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

• 选择数组还是链表？

1.插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点
1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。
3.链表缺点
1）内存空间消耗更大，因为需要额外的空间存储指针信息。
2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。
4.如何选择？
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。
如果代码对内存的使用非常苛刻，那数组就更适合。

• 应用

1.如何分别用链表和数组实现LRU缓冲淘汰策略？
1）什么是缓存？
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
2）为什么使用缓存？即缓存的特点
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。
3）什么是缓存淘汰策略？
指的是当缓存被用满时清理数据的优先顺序。
4）有哪些缓存淘汰策略？
常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。
5）链表实现LRU缓存淘汰策略
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。
6）数组实现LRU缓存淘汰策略
方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）
2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如 上海自来水来自海上）
1）前提：字符串以单个字符的形式存储在单链表中。
2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3）将链表中的字符倒序存储一份在另一个链表中。
4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。
六、设计思想
时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

3、队列

什么是队列:

队列是一种受限的线性表数据结构,只支持两个操作:入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

特点:

1 . 队列跟栈一样,也是一种抽象的数据结构。

2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

实现:

队列可以用数组来实现,也可以用链表来实现。

用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

基于数组的队列:

实现思路:

实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

基于链表的实现: 

需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

循环队列:

我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。

我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:

队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,

就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

解决浪费一个存储空间的思路:定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++

阻塞队列和并发队列(应用比较广泛)

阻塞队列其实就是在队列基础上增加了阻塞操作。

简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

小结:

队列最大的特点就是先进先出,主要的两个操作是入队和出队。

它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。

4、递归算法

一、什么是递归？

1.递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
2.方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
3.基本上，所有的递归问题都可以用递推公式来表示，比如
f(n) = f(n-1) + 1; 
f(n) = f(n-1) + f(n-2);
f(n)=n*f(n-1);

二、为什么使用递归？递归的优缺点？

1.优点：代码的表达力很强，写起来简洁。
2.缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

三、什么样的问题可以用递归解决呢？

一个问题只要同时满足以下3个条件，就可以用递归来解决：
1.问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。
2.问题与子问题，除了数据规模不同，求解思路完全一样
3.存在递归终止条件

四、如何实现递归？

1.递归代码编写
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
2.递归代码理解
对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。
那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归的关键是终止条件
五、递归常见问题及解决方案

1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。
2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。

六、如何将递归改写为非递归代码？

笼统的讲，所有的递归代码都可以改写为迭代循环的非递归写法。如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。

5、排序

一、排序方法与复杂度归类
（1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
（2）复杂度归类
冒泡排序、插入排序、选择排序 O(n^2)
快速排序、归并排序 O(nlogn)
计数排序、基数排序、桶排序 O(n)

二、如何分析一个“排序算法”？
<1>算法的执行效率
1. 最好、最坏、平均情况时间复杂度。
2. 时间复杂度的系数、常数和低阶。
3. 比较次数，交换（或移动）次数。
<2>排序算法的稳定性
1. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
2. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。
3. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。
<3>排序算法的内存损耗
原地排序算法：特指空间复杂度是O(1)的排序算法。

常见的排序算法:

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。

代码:

  public int[] bubbleSort(int[] a) {
        int n = a.length;
        if (n<=1) {
            return a;
        }
        for (int i = 0; i < n; i++) {
            //提前退出冒泡循环的标志
            boolean flag = false;
            for (int j = 0; j < n-i-1; j++) {
                if (a[j]>a[j+1]) {//
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;

                    flag = true;//表示有数据交换
                }
                if (!flag) {
                    break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
                }
            }
        }
        return a;
    }

四、插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。

代码:

    public int[] insertionSort(int[] a) {
		int n = a.length;
		if (n<=1) return a;
		
		for (int i = 1; i < n; i++) {
			int value = a[i];
			int j = i-1;
			for (; j >=0; j--) {
				if (a[j] > value) {
					a[j+1] = a[j];//移动数据
				}else {
					break;
				}
			}
			a[j+1] = value;//插入数据
		}
		
		return a;
	}

五、选择排序

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
代码:

public int[] selectionSort(int[] a) {
		int n = a.length;
		
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i+1; j < a.length; j++) {
				//交换
				if (a[i] > a[j]) {
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
		}
		
		return a;
	}

六、归并排序

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

 实现思路:

merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

代码:

 // 归并排序算法, a是数组，n表示数组大小
  public static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n-1);
  }

  // 递归调用函数
  private static void mergeSortInternally(int[] a, int p, int r) {
    // 递归终止条件
    if (p >= r) return;

    // 取p到r之间的中间位置q
    int q = (p+r)/2;
    // 分治递归
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q+1, r);

    // 将A[p...q]和A[q+1...r]合并为A[p...r]
    merge(a, p, q, r);
  }

  private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q+1;
    int k = 0; // 初始化变量i, j, k
    int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
   
    // 1 排序
    while (i<=q && j<=r) {
      if (a[i] <= a[j]) {
        tmp[k++] = a[i++]; // i++等于i:=i+1
      } else {
        tmp[k++] = a[j++];
      }
    }

    // 2 判断哪个子数组中有剩余的数据
    int start = i;
    int end = q;
    if (j <= r) {
      start = j;
      end = r;
    }

    // 3 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
      tmp[k++] = a[start++];
    }

    // 4 将tmp中的数组拷贝回a[p...r]
    for (i = 0; i <= r-p; ++i) {
      a[p+i] = tmp[i];
    }
  }

merge是这样执行的:

代码分析:

七、快速排序

快排的思想:    如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

快排利用的分而治之的思想

八、线性排序:

时间复杂度O(n)

我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

特点:

非基于比较的排序算法 

桶排序

桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

对排序的数据要求苛刻:

1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

2 ,数据在各个桶之间的分布是比较均匀的。

3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限，无法将数据全部加载到内存中。

计数排序

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

代码:

 // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
  public static void countingSort(int[] a) {
	int n = a.length;
    if (n <= 1) return;

    // 查找数组中数据的范围
    int max = a[0];
    for (int i = 1; i < n; ++i) {
      if (max < a[i]) {
        max = a[i];
      }
    }

    // 申请一个计数数组c，下标大小[0,max]
    int[] c = new int[max + 1];
    for (int i = 0; i < max + 1; ++i) {
      c[i] = 0;
    }

    // 计算每个元素的个数，放入c中
    for (int i = 0; i < n; ++i) {
      c[a[i]]++;
    }

    // 依次累加
    for (int i = 1; i < max + 1; ++i) {
      c[i] = c[i-1] + c[i];
    }

    // 临时数组r，存储排序之后的结果
    int[] r = new int[n];
    // 计算排序的关键步骤了，有点难理解
    for (int i = n - 1; i >= 0; --i) {
      int index = c[a[i]]-1;
      r[index] = a[i];
      c[a[i]]--;
    }

    // 将结果拷贝会a数组
    for (int i = 0; i < n; ++i) {
      a[i] = r[i];
    }
  }

散列表

什么是散列表:

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

原理:

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

散列函数的设计要求:

1. 散列函数计算得到的散列值是一个非负整数;.
2. 如果key1 = key2,那hash(key1) == hash(key2);
3. 如果key1 != key2,那hash(key1)  !=  hash(key2),

散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

解决散列冲突的方法有两种: 

开放寻址法(open addressing)和链表法(chaining)

开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

链表法:

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。