归并排序是分而治之思想的典型应用。1 你会学到什么清楚地搞懂常常会用到的排序算法的根本思想, 算法有关时间以及空间这方面的复杂度, 还包括怎样去挑选这些排序算法, 明确出针对要解决的问题来说的最佳排序算法情形下, 现已归总了冒泡排序以及其经过改变以后的也就是快速排序这一算法, 直白的选择排序以及堆排序算法, 归总了从直接插入排序一直到希尔排序所进行的改变情况, 接下来要归总归并排序。2 讨论的问题是什么各种排序算法具备的基本思想, 探讨各种排序算法之时、空复杂度, 还有算法的稳定性, 算法是怎样得以改进的, 例如冒泡排序是怎么样改进成为当下最为常用的快速排序的, 直接选择排序至堆排序的改进情况, 直接插入排序到希尔排序的优化之处, 下面对归并排序展开讨论。3 相关的概念和理论内部排序要是整个排序的过程, 不需要去访问外存就能够完成, 那就把这样的排序问题, 称作是内部排序。外部排序如果参与排序的记录数量非常大, 整个序列的排序过程没办法在内存里完成, 那么就把这样的排序问题称作外部排序。就地排序如果排序算法所需要利用的辅助空间, 并不依靠问题的规模n, 也就是说辅助空间是O1, 那么就称作就地排序。稳定排序假设在要进行排序的记录序列当中, 有多个具备相同关键字的记录, 要是经过排序之后, 这些记录的相对顺序维持不变, 也就是说在原本的序列里 rirj, ri 在 rj 之前, 而在排序完成后的序列中, ri 依旧在 rj 之前, 那么就称这种排序算法是稳定的反之假若不是这样, 那就称作是不稳定的。排序序列分布排序时, 需要考量待排序关键字的分布情形, 这会对排序算法的选择产生影响, 一般而言, 我们于分析下述算法时, 皆需考虑关键字分布为随机分布, 而非依照某种规律分布, 诸如正态分布之类的。待排序序列排序序列中剩余即将要排序的序列部分。已排序序列排序序列中已经排序好的序列部分。4 归并排序过程详解 归并简介归并排序英文名称是MERGE-SORT。它是一种有效的排序算法, 这种算法是建立在归并操作之上的, 并且归并排序算法是采用分治法的, 是分治法一个相当典型的应用。把业已有序的子序列予以合并, 从而获取全然有序的序列, 也就是说首先要让每一个子序列有序, 接着要让子序列段之间有序。算法的核心概念—二路归并若将两个有序表合并成一个有序表称为二路归并。二路归并比较 a和 b的大小若 a≤b则将第一个有序表中的元素a复制到 r放入中, 且让i加上1, 同时让k加上1不然把第二个有序表里头的元素b。复制到r中并令 j 和 k 分别加上1如此循环下去直到其中一个有序表取完之后, 再把另一个呈现有序状态的表里面剩余的那些元素, 复制到r之中, 从下标k开始直至下标t的单元。这个过程请见下面的例子演示。二路归并演示如下图所示初始状态时a序列2,3,5和b序列2,9存在已排序好的子序列, 当下借助二路归并把a与b合并成有序序列r, 起初, i指向a的首个元素, j指向b的首个元素, k的初始值为0。说明r中最后一个元素起到哨兵的作用灰色显示。第一步比较a和b假如发现呈现出相等的情况, 要是规定在相等之际是a优先进入r的话, 那么就这般如图所示, i会增加1, k也会增加1, 为了达成形象化的目的, 归并之后的元素便不再进行绘制了。第二步继续比较此时b小所以b的元素2进入r则如下图所示j, k分别加1第三步继续比较此时a小所以a的元素3进入r则如下图所示i, k分别加1第四步继续比较此时a由于小, 致使a的元素5进入r, 于是便如下图所示那般, i、k分别加1, 此时序列a的3个元素已然归并完毕, b中尚剩下一个, 这能够借助k瞧出, 它尚未抵达个数5。第五步, 把序列b里的全部剩余元素, 直接放到r中就行, 不需要做任何比较了, 一直到b变空, 此时二路归并就结束了。总体思路归并排序的算法我们通常用递归实现。先把待排序区间s,t以中点二分接着把左边子区间排序再把右边子区间排序最后把左区间和右区间用一次归并操作合并成有序的区间s,t完整例子待排序列被运用在, 我们仍会采用的冒泡排序以包括其改进后的算法, 涉及快速排序算法以内, 还有在同样被参考利用的直接选择排序当中, 关乎与其相关方面的堆排序算法方面里, 更包含了从直接插入排序一直到做到改进过后的希尔排序所对应的这三篇之中被用到的。3 2 5 9 2伪代码sort(unsorted, start, end, sorted) { if(startend) { mid start (end-start)/2; //分隔区间 sort(unsorted, start,mid,sorted); sort(unsorted,mid1,end,sorted); merge(unsorted,start,mid,end,sorted); } }过程模拟下图所演示的, 是归并排序递归版本当中, 第一次执行二路归并且时展示的示意图, 需要留意地去观察右图的栈的入栈顺序, 依据此可观看到sort的入栈顺序, 而且当执行一回merge的时候必定是存在2个sort返回并处于有序状态了, 就如同下边这张图呈现的这般, sort。0,0和sort1,1是在所有递归因返回满足start条件而得的返回情况都达成之后呀在执行至merge部位, 待merge执行完毕之后紧接着就要去执行sort。0,1出栈此时的栈顶为sort0,2函数, 能瞧出它的前半部分已然计算完毕, 仅需计算后半部分, 就是第二个sort, 接着再次进行merge, 然后sort。0,2出栈。。。如下是上个例子里归并排序的完整示例, sort的示意图, merge的示意图, 能看到最后一次merge, 恰恰是上面所讲的二路。2,3,52,9的归并排序如果不熟的可以回过头再看看。5 算法评价因递归每次按一半分区, 且merge需线性时间, 所以归并排序的时间复杂度为O(nlogn)。最为关键的是该算法里最好、最坏以及平均的时间性能皆是O(nlogn)。归并排序的空间复杂度为O(n)会占用内存。总归而言, 归并排序尽管占有内存算是挺多, 然而它是那种效率高并且稳定的算法。6 总结归并排序的时间复杂度, 于最坏情况下是O(nlogn), 于最好情况下一样为O(nlogn), 在平均情形下同样是O(nlogn), 它属于那样一种排序算法, 其效率以及性能是非常良好的。只是它需占据 O(n)的内存空间, 要是数据量一旦特别大, 内存或许承受不住, 这是它的弱点以及致命之处。然而其他排序算法, 像快速排序, 希尔排序, 皆是就地排序的算法, 它们不会占用额外的内存空间。然而, 这个存在占用内存情况的弱点, 能够被改进成为就地排序, 要是大家有兴趣, 能够去查看一番。
