当前位置:天才代写 > tutorial > Python教程 > python 算法之归并排序-python基础

python 算法之归并排序-python基础

2021-02-24 12:05 星期三 所属: Python教程 浏览:16

归并排序

归并排序(Merge sort)是创建在合并实际操作上的一种合理的快速排序算法。该优化算法是选用分治法(Divide and Conquer)的一个十分典型性的运用。

做为一种典型性的分而治之观念的优化算法运用,归并排序的完成由二种方式:

由上而下的递归(全部递归的方式都能够用迭代更新重写,因此 就拥有第 2 种方式);

由上而下的迭代更新;

在《数据结构与算法 JavaScript 描述》中,创作者得出了由上而下的迭代更新方式。可是针对递归法,创作者却觉得:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
殊不知,在 JavaScript 中这类方法不太行得通,由于这一优化算法的递归深层对它而言太深。

说真话,我不会太了解这句话。意思是 JavaScript c语言编译器运行内存很小,递归过深非常容易导致内存溢出吗?敬请有高手可以赐教。

和选择排序一样,归并排序的特性不会受到键入数据信息的危害,但主要表现比选择排序好的多,由于自始至终全是 O(nlogn) 的算法复杂度。成本是必须附加的存储空间。

优化算法流程

  1. 申请空间,使其尺寸为2个早已排列编码序列之和,该室内空间用于储放合拼后的编码序列;
  2. 设置2个表针,最开始部位各自为2个早已排列编码序列的起止部位;
  3. 较为2个表针所偏向的原素,挑选相对性小的原素放进到合拼室内空间,并挪动表针到下一部位;
  4. 反复流程 3 直至某一表针做到编码序列尾;
  5. 将另一序列剩余的全部原素立即拷贝到合拼编码序列尾。

Python 编码完成

def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:] return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
result = [] while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result

 

    关键字:

天才代写-代写联系方式