归并排序(Merge sort)

xiaoxiao2021-02-27  827

Time complexity:O(logn)

方法:二路归并(2-way merge)

对象:有序序列(sorted sequence), 即可以是有序向量(sorted vector),也可以是列表(list)算法性质:迭代

步骤: 1.无序向量的递归分解(递归) 2.有序序列的逐层归并(迭代)

算法描述:(摘自Oxford一哥们写的DS教材~)

“Divide and conquer ” Merge sort has three steps to sort an input sequence S with n elements:

Divide—partition S into two sequences S1 and S2 of about n/2 elements each Recur—recursively sort S1 and S2Conquer—merge S1 and S2 into a sorted sequence
转载请注明原文地址: https://www.6miu.com/read-656.html

最新回复(0)