当问题规模数据大量增加时，重复执行的次数也必定会增加，那么我们就有必要关心执行次数是以什么样的数量级增加，这也是分析时间复杂度的意义，是一个非常重要衡量算法好快的事前估算的方法,常见的时间复杂度：,常见的排序算法这里总结四种最具代表性的：,冒泡排序是一种简单的排序算法，它需要重复的走访序列，一次只比较两个数据，如果顺序错误则交换这两个数据，直到没有在需要交换的数据，走访结束，具体算法描述如下：,冒泡排序改进方案：,方案一：设置一个标记变量pos，用来记录每次走访的最后一次进行交换的位置，那么下次走访之后的序列便可以不再访问。,方案二：传统冒泡一趟只能找到一个最大或者最小值，我们可以考虑在利用每趟排序过程中进行正向和反向冒泡，一次可以得到一个最大值和最小值，从而使排序趟数几乎减少一半。,以上提供两种改进冒泡的思路，耗时在这只是进行粗略对比，并不完全确定好坏，相比之下改进后的冒泡时间复杂度更低，下图实例展示结果耗时更短。,快速排序是分治策略的经典实现，也是对冒泡排序的改进，出现频率较高，基本思路是经过一趟排序，把数据分割成独立的两部分，其中一部分数据要比另一部分都小，然后按此方法继续排序，以达到整个序列有序，具体算法描述如下：,第一个突破O(n^2)的排序算法;是简单插入排序的改进版;与插入排序的不同点在于，它会优先比较距离较远的元素。希尔排序又叫做增量缩小排序，核心在于间隔序列的设定，既可以提前设定好间隔序列，也可以动态的定义间隔序列，后者是《算法(第四版)》中提出的，实现如下：,归并排序不受输入数据的影响，时间复杂度始终都是O(nlogn)，但代价是需要额外的内存空间。归并排序也是分治法的经典体现，先使子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为2-路归并。实现如下：,线性查找较简单，只需要简单遍历即可。,时间复杂度：最佳情况O(n)，最差情况O(n)，平均情况O(n),也叫作折半查找，要求查找表的数据实现线性结构存储，还要求查找表中的顺序是有序的,时间复杂度分析：最佳情况O(logn)，最差情况O(logn)，平均情况O(logn)。,二叉树遍历有四种方式：先序遍历，中序遍历，后序遍历，层序遍历。,前序遍历：先访问根节点，然后前序遍历左子树，再前序遍历右子树。,中序遍历：先中序遍历左子树，然后访问根节点，最后遍历右子树。,后序遍历：从左到右，先叶子后结点的方式遍历访问左子树，最后访问根节点。,层序遍历：从根结点从上往下逐层遍历，在同一层，按从左到右的顺序对结点逐个访问。,有两种通用的遍历树的策略：,正如名字一样，深度优先遍历采用深度作为优先级，从某个确定的叶子，然后再返回根到另个分支，有细分为先序遍历，中序遍历和后序遍历,广度优先按照高度顺序一层一层访问整棵树，高层次的结点会比低层的结点先访问到
© 版权声明
文章版权归作者所有，未经允许请勿转载。
