- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
分治法典型应用，分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。
处理过程是由下到上的，先处理子问题，然后再合并。
如果感觉自己对递归掌握的还不是很透彻的同学，可以移步我的这篇专栏你真的懂递归吗？。
顾名思义，分而治之。一般分为以下三个过程：
- 分解：将原问题分解成一系列子问题。
- 解决：递归求解各个子问题，若子问题足够小，则直接求解。
- 合并：将子问题的结果合并成原问题。
归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来，这样整个数组就都有序了。
constmergeSort=function(arr){constmerge=(right,left)=>{constresult=[]leti=0,j=0while(i<left.length&&j<right.length){if(left[i]<right[j]){result.push(left[i++])}else{result.push(right[j++])}}while(i<left.length){result.push(left[i++])}while(j<right.length){result.push(right[j++])}returnresult}constsort=(arr)=>{if(arr.length===1){returnarr}constmid=Math.floor(arr.length/2)constleft=arr.slice(0,mid)constright=arr.slice(mid,arr.length)returnmerge(mergeSort(left),mergeSort(right))}returnsort(arr)}
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)
- 稳定
Metadata
Metadata
Assignees
Labels
No labels