怎样做才能让百度前两页有自己网站内容,服装 多语言 网站源码,app store下载正版,助企建站学习归并排序的过程是十分痛苦的。它并不常用#xff0c;看起来时间复杂度好像是几种排序中最低的#xff0c;比快排的时间复杂度还要低#xff0c;但是它的执行速度不是最快的。很多朋友不理解时间复杂度低为什么运行速度不一定快#xff0c;这个不清楚的伙伴可以看下我之…学习归并排序的过程是十分痛苦的。它并不常用看起来时间复杂度好像是几种排序中最低的比快排的时间复杂度还要低但是它的执行速度不是最快的。很多朋友不理解时间复杂度低为什么运行速度不一定快这个不清楚的伙伴可以看下我之前发表的文章http://www.cnblogs.com/Lin-Yi/p/7301535.html看完之后也许你会对时间复杂度有一个新的认识。我谈的观点往往不是官方的定义我希望能帮助更多基础薄弱的同学读懂思想~归并排序先分开再合并分开成单个元素合并的时候按照正确顺序合并假如我们有一个n个数的数列下标从0到n-1首先是分开的过程1 我们按照 n//2 把这个数列分成两个小的数列2 把两个小数列 再按照新长度的一半 把每个小数列都分成两个更小的。。。一直这样重复一直到每一个数分开了比如 6 5 4 3 2 1第一次 n6 n//23 分成 6 5 4 3 2 1第二次 n3 n//21 分成 6 5 4 3 2 1第三次 n1的部分不分了n2 n//21 分成 5 4 2 1之后是合并排序的过程3 分开之后我们按照最后分开的两个数比较大小形成正确顺序后组合绑定刚刚举得例子 最后一行最后分开的数排序后绑定 变成 4 5 1 2排序后倒数第二行相当于把最新分开的数排序之后变成 6 4 5 3 124 对每组数据按照上次分开的结果进行排序后绑定6 和 4 5(两个数绑定了) 进行排序3 和 1 2(两个数绑定了) 进行排序排完后 上述例子第一行待排序的 4 5 6 1 2 3 两组数据5 对上次分开的两组进行排序拿着 4 5 6 1 2 3两个数组进行排序每次拿出每个数列中第一个(最小的数)比较把较小的数放入结果数组。再进行下一次排序。每个数组拿出第一个数小的那个拿出来放在第一位 1 拿出来了 变成4 5 6 2 3每个数组拿出第一个书比较小的那个放在下一个位置 1 2被拿出来 待排序 4 5 6 2每个数组拿出第一个书比较小的那个放在下一个位置 1 2 3 被拿出来 待排序 4 5 6如果一个数组空了说明另一个数组一定比排好序的数组最后一个大 追加就可以结果 1 2 3 4 5 6相当于我们每次拿到两个有序的列表进行合并分别从两个列表第一个元素比较把小的拿出来在拿新的第一个元素比较把小的拿出来这样一直到两个列表空了 就按顺序合并了两个列表结束时间复杂度 最好最坏都是 O( n log n )稳定性稳定缺点每次拆分数组都要开心的数组 每次合并数组都要开新数组空间复杂度很大在python中这样实现def merge_sort( li ):#不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素不再拆分了if len(li) 1:return li#取拆分的中间位置mid len(li) // 2#拆分过后左右两侧子串left li[:mid]right li[mid:]#对拆分过后的左右再拆分 一直到只有一个元素为止#最后一次递归时候ll和lr都会接到一个元素的列表# 最后一次递归之前的ll和rl会接收到排好序的子序列ll merge_sort( left )rl merge_sort( right )# 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表# 这里我们调用拎一个函数帮助我们按顺序合并ll和lrreturn merge(ll , rl)#这里接收两个列表def merge( left , right ):# 从两个有顺序的列表里边依次取数据比较后放入result# 每次我们分别拿出两个列表中最小的数比较把较小的放入resultresult []while len(left)0 and len(right)0 :#为了保持稳定性当遇到相等的时候优先把左侧的数放进结果列表因为left本来也是大数列中比较靠左的if left[0] right[0]:result.append( left.pop(0) )else:result.append( right.pop(0) )#while循环出来之后 说明其中一个数组没有数据了我们把另一个数组添加到结果数组后面result leftresult rightreturn resultif __name__ ‘__main__‘:li [5,4 ,3 ,2 ,1]li2 merge_sort(li)print(li2)算法过程理解起来非常痛苦 呜呜好委屈不过我希望大家静下心来一点点学一定会有所收获
