最近有好多同学一直问我一些基础的问题，想了想，还是抄抄冷饭，聊聊基础。
数据结构方面的内容，讲道理说实话，网上能找到的免费的资源大把，多到我一开始都不想写这个系列。
而且还有清华大学等顶级高校教授在网上录制的网课，这个就比较尴尬了，比专业我肯定是比不过人家教授讲的。
所以这个系列的名字起的就比较有意思了，叫「一本正经的聊数据结构」。
讲正经的讲不过，但是我可以讲不正经的啊。
车开的有点远了，拐回来给想正经学习的同学推荐几本书，同时也是豆瓣上的数据结构评分最高的。
「清华大学计算机系列教材:数据结构(C++语言版)(第3版)」这本书是邓俊辉教授编写的，同时配备了免费的视频，非常不错，对新人非常友好。
「数据结构与算法分析」这本书是一位美国教授写的，这本书的原书曾被评为20世纪顶尖的30部计算机著作之一，也是经典中的经典，就是有点厚。
「算法导论」这本书的范畴其实已经不是数据结构，而是算法了，但是数据结构和算法不分家嘛，我就也一起放在这里了，这本书同样也是经典中的经典，并且在美国被广泛的应用于本科生阶段，成为了本科生的教材的同时也成为了他们的噩梦。对于想买的同学我这里稍微泼点凉水，在买这本书之前最好先问问自己数学学得咋样，因为是讲算法，它的设计思想完全依托于背后的数学结构，它运作的机制以及它的美，也都来自它的数学。最好再问问自己的毅力如何，因为这本书非常的厚，特别适合用来垫显示器，别问我为啥，都是痛。
时间复杂度杂七杂八的讲完了，终于到正题了。
说道数据结构，第一个要提的概念就是时间复杂度和空间复杂度。
为什么我不谈空间复杂度呢？
因为简单，对的，就是这么耿直。
说点靠谱的，因为现在存储空间不值钱了，现在不是20年前，想想那个年代的红白机，一个游戏K大小，什么「魂斗罗」、「忍者必须死」、「坦克大战」，好像我又暴露童年了。
还有就是因为就渐进复杂度的意义而言，在任一算法的任何一次运行过程中所消耗的存储空间，都不会多于其间所执行基本操作的累计次数。整个算法所需的空间总量，也不过与基本操作的次数同阶。从这个意义上说，时间复杂度本身就是空间复杂度的一个天然的上限。
当然，对于输入的数据极其庞大的时候，由于时间复杂度确立的上限已经无法接受了，这种情况下，人们主要的做法是努力优化算法，比较常见的思路是空间换时间，背后的原因就是空间不值钱了。
顺便再歪一下，服务器的内存可能很多同学都没有概念。
emmmmmmmmmm，你们见过内存GB，GB，1TB的电脑么？
没错，就是服务器。
那么，什么是时间复杂度呢？
这就要说到排序算法了，冒泡排序，学过程序的人接触的第一个算法一定是这个。
如果有其他的算我没说。
为什么要选择排序算法呢？
因为用的多啊，平时我们接触的也很多，很多时候是你接触到了排序，但是你却没有意识到。
比如某点评、某团的外卖软件，你打开点外卖的时候，是不是会有什么综合排序，距离排序，评价排序之类的。或者说我们最常用的百度，使用某个关键字搜索后，是不是会按照某些规则将结果排序后展现在你的面前。
简单的介绍下冒泡排序：
在由一组整数组成的序列A[0,n-1]中，满足A[i-1]=A[i]的相邻元素称作顺序的；否则是逆序的。不难看出，有序序列中每一对相邻元素都是顺序的，亦即,对任意1=in都有A[i-1]=A[i]；反之，所有相邻元素均顺序的序列，也必然整体有序。
冒泡排序的核心是扫描交换，从前向后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。对于长度为n的序列，共需做n-1次比较和不超过n-1次交换，
我知道你们没看懂，下面给你们搞了个动图：
时间复杂度是用来衡量一个算法的所需要的计算时间的，但是运行的时间是由多种因素综合而成的。
就拿排序来举例子，对于输入的数据量的不同，每个元素的次序的不同，每个元素数值大小的不同，都会对最终的排序时间造成影响。
比如你输入一串完全倒序的数字，如：{9,8,7,6,5,4,3,2,1}，和一串仅有一位顺序不对，如：{1,2,3,4,5,6,7,9,8}，这两串数字排序所需要的时间肯定是不同的。
还有数据量大小，实际上数据量大小是决定耗时的主要原因，一万个数字做排序和一亿个数字做排序，这其中所耗费的时间天差地别，实际上，在数据量大小比较接近的时候，相应的计算的耗时也越接近。
时间消耗的变化趋势可以表示为一个函数，这个函数称为这个算法的时间复杂度。
那么就有了这么一条定义：在规模为n的所有输入中选择执行时间最长者作为T(n)，并以T(n)度量该算法的时间复杂度。
这句话记住就完了，没啥原因，就是这么定义的。
小学数学课本上的定理啥时候跟你讲过原因，啥叫定理，定理的意思是就这么定义的。
我们可以在实际环境中直接测得的执行时间T(n)，虽然可行是可行，但是作为评判不同算法性能优劣的标准，这个操作有点不切实际啊。
同一个算法，同样的输入数据，在不同的硬件平台上，或者不同的系统平台上，甚至是在不同的时间上，测试所消耗的时间都是不一样的，有不信邪的同学可以简单写一个循环进行累加计算，多循环几圈，比如先循环个次，计算一下消耗的纳秒数，甚至是毫秒数，多运行几次，看看能有多少次消耗的时间是一样的。
相信我，运行10次是可能得到10个不同的消耗的时间。
一种自然且可行的解决办法是，将时间复杂度理解为算法中各条指令的执行时间之和。在图灵机（TuringMachine,TM）和随机存储机（RandomAccessMachine,RAM）等计算模型中，指令语句均可分解为若干次基本操作，比如算术运算、比较、分支、子程序调用与返回等；而在大多数实际的计算环境中，每一次这类基本操作都可在常数时间内完成。
如此，不妨将T(n)定义为算法所执行基本操作的总次数。也就是说，T(n)决定于组成算法的所有语句各自的执行次数，以及其中所含基本操作的数目。——来源：「数据结构」邓俊辉
我们来拆解一下刚才冒泡排序的时间复杂度，数学功底不好的同学这一段可以跳过，直接看后面的结果，这里我们先简单的写一个冒泡排序，我这里就用Python写了，有编程基础的同学应该都能看得懂：
defbubbleSort(nums):foriinrange(len(nums)-1):forjinrange(len(nums)-i-1):ifnums[j]nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]returnnumsnums=[5,2,45,6,8,2,1]print(bubbleSort(nums))
可以看到，在上面这一段代码中，冒泡排序是由两层循环套起来的，看循环，先找到最内层，从内层往外看。
在最内层，从前向后，依次比较各对相邻元素，如有必要则将其交换。那么在每一轮内循环中，需要扫描和比较n-1对元素，至多需要交换n-1对元素。元素的比较和交换，都属于基本操作，故每一轮内循环至多需要执行2(n-1)次基本操作。
接着看外层，外层就比较简单了，直接是最多循环n-1次。
那么，总共需要执行的基本操作不会超过2(n-1)^2次。
表达式我们可以这么写：
学过小学数学的我们可以对它做一个化简：
那么，到这里就结束了么？当然没有，因为时间复杂度我们