西部数码做跳转网站,百度seo排名培训优化,wordpress 严重 漏洞,张家港建网站的公司小智最近迷上了计算机算法#xff0c;今天过来给大家讲讲排序算法。准备讲排序算法之前#xff0c;我们还是要先回顾一下排序这个概念。排序是一门古老的科学。排序问题#xff0c;用数学的方式可以表达如下问题输入#xff1a;给定n个数#xff0c;a1, a2, a3, ..., an… 小智最近迷上了计算机算法今天过来给大家讲讲排序算法。准备讲排序算法之前我们还是要先回顾一下排序这个概念。排序是一门古老的科学。排序问题用数学的方式可以表达如下问题输入给定n个数a1, a2, a3, ..., an要求输出给出n个数的排列a1, a2, a3, ..., an使得 a1 ≤ a2 ≤ a3 ≤ ... ≤ an。从更形象的角度来说排序就是一群人站成一列高的站前面矮的站在后面。一个家庭的所有成员按身高排列的示意图小智实在找不到图了画一个示意-_-关于排序有几个描述算法特征的词语稳定如果a原本在b前面而ab排序之后a仍然在b的前面不稳定如果a原本在b的前面而ab排序之后a可能会出现在b的后面时间复杂度一个算法执行所耗费的时间。空间复杂度运行完一个程序所需内存的大小。ok了解完排序的相关概念以后我有一个新的问题了如何评价一个算法小智认为可以用一个词语来形容一个优秀的算法多快好省。什么是“多快好省”我们从算法的角度来解析一下多能够可靠处理大规模的数据快算法的时间复杂度要更低的好算法实现要符合稳定性省算法的空间复杂度要更低的到底哪些算法能够符合“多快好省”这个目标呢我们先看一下目前的算法分类基于比较的排序算法的特征总结注本文不讨论非基于比较算法比如计数排序、桶排序和基数排序“多”的角度从数据量的处理性能来看需要不受随机因素影响的算法。冒泡算法、插入排序、快速排序这三个算法最好情况和最坏情况相差了一个数量级这种不可靠性可能影响数据处理的效率。“快”的角度从时间复杂度的角度来看希尔排序、归并排序、快速排序、堆排序的算法复杂度比较好均低于O(n2)。“好”的角度从稳定性的角度来看归并排序、插入排序、冒泡排序是稳定的“省”的角度从空间复杂度的角度来看冒泡排序、插入排序、希尔排序、堆排序空间复杂度为O(1)。其中值得注意的是一般写法的归并排序空间复杂度为O(n)经过优化以后使用空间可以为O(1)。大家都看出了我的倾向了吧小智从“多快好省”这四个方面分析发现归并算法在这四个方面表现不错。这次小智决定跟大家探讨一下归并算法。为什么归并排序能够做到多快好省解答这个问题之前我们先了解一下什么是归并排序。归并算法merge sort是一个分治算法divide and conquer algorithm冯·诺依曼John von Neumann 在1945年发明了这个算法。这个算法将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。实际上归并算法的算法步骤非常简单第1步拆分把长度为n的输入序列分成两个长度为n/2的子序列第2步递归调用对这两个子序列分别使用归并排序第3步合并将两个排序好的子序列合并成一个最终的排序序列这几步我们来分别地讲一下什么是拆分将一个长序列拆分成两个子序列。这个属于分治法中的“分”将大问题降解为小问题。将长序列拆分成两个子序列示意图如果n为奇数不能被2整除可以将n/2向上取整这个对算法没有影响。有一个特殊情况是需要注意的当子序列长度为1时已经没有办法进行拆分了可以直接执行下一步。什么是递归调用实际上是重复调用归并排序的程序。我们假想一下在最开始的情况下执行完第1步长序列被拆分为2个子序列。接着执行第二步时直接对子序列进行归并排序那么下一步则是继续拆分子序列。如此下去直至将长序列拆分到无法分拆的情形。我们以图来说明会更加清晰一点归并算法递归调用的分拆效果经过不断地递归调用要处理的子序列长度越来越短最后直至子序列长度为1。有一个特殊情况是需要注意的当子序列长度为1时已经不需要继续调用归并排序了因此可以直接跳过递归调用这个步骤。什么是合并是将两个排好序的子序列合成一个也是排好序的序列。这个合并算法也是比较简单。合并过程可以表述为对于两个子序列X和Y其中X和Y都是升序排列以及知道X和Y每个数据在原来长序列的位置分别为Xp和Yp如何将X和Y合并成一个稳定的升序排列由于这两个子序列都是升序排列因此我们同时遍历这两个子序列从遍历的位置各拿出一个数字哪个数字小就把它拿出来插入合并序列中。如果遇到拿出来的两个数字相等的情况则比较原来序列的位置哪个小就把它拿出来即可。按照上述合并步骤我们可以写出合并伪代码了i 1, j 1, l 1申请一个临时变量temp用于储存合并后序列如果 X[i] Y[j]: temp[l] X[i], l l 1, i i 1如果 X[i] Y[j]: temp[l] Y[j], l l 1, j j 1如果 X[i] Y[j]: 如果 Xp[i] Yp[j]: temp[l] X[i], l l 1, i i 1 如果 Xp[i] Yp[j]: temp[l] Y[j], l l 1, j j 1我将合并流程补充到整个归并算法的执行流程当中以图的形式做了一个示例归并排序整体流程示意图归并排序我们了解完了我们可以开始回答为什么归并排序能够表现如此出色“多”的角度归并排序为什么能保证可靠地处理数据归并排序的拆分的流程跟数据的原始排序没有关系无论是最坏情况还是最好情况时间复杂度都是一致的能够稳定处理大量数据。“快”的角度归并排序的时间复杂度为什么是 O(n log n)?设归并排序所消耗的时间为T(n)进行归并排序的拆分操作以后将原来的问题划分为原来规模的二分之一每一个划分出来的问题将耗费时间是T(n/2)最后把这两部分有序的数组合并在一起所花的时间为O(n)因此T(n) 2×T(n/2) O(n)而划分次数最多可以有log2 n次因此累加起来可得T(n) O(n log n)“好”的角度归并排序为什么能保证稳定呢归并排序将序列分割到最小而后将序列进行合并。假如两个数字是相等的在分割子序列的时候不会更改他们之间的相对位置在合并子序列的时候只要能够做到先将位置在前的数字放到合并数组这样就保证了排序结果的稳定。“省”的角度归并排序为什么空间复杂度可以为O(1)归并排序虽然原始写法的确是这样的但是算法是可以改造的我们只需要做到原地排序就可以了而对于归并排序而言原地排序的关键是合并。归并排序的原来写法当进行合并时是申请一个临时空间将合并的数据放到临时空间当中这个算法复杂度为 O(n) 。实际上合并过程可以直接使用已有的位置。假设我们要合并的两段数组还是[13, 23, 37, 54]和[11,17, 26,29]在归并算法里它们可以看成一个连续的数组形式[13, 23, 37, 54, 11, 17, 26, 29]首先我们检查两段数组的第一个数发现13 11那么11这个数要拿出来原来是要放到临时空间的第一个位置但我们可以利用数组已有的位置将11直接移到数组的第一个位置然后原来第一段数组往后移一个位置这样数组变为[11, 13, 23, 37, 54, 17, 26, 29]而后我们继续按照这种方式合并[13, 23. 37. 54]和[17, 26 29]这两段数组。可以发现这种方式空间复杂度只需一个临时变量用于协助数字移动因此空间复杂度为O(1)。当然这样优化增加了移动的次数为了空间就要损失时间了。总结一下归并排序是个宝一个多快好省的排序算法大家如果遇到数据排序问题可以优先考虑它。当然归并排序并不是全能的在某些类型问题下有些算法比归并排序表现更为出色往后小智会给大家解读。
