小撒是一只好學(xué)的小鴨子萍嬉，這天嚎朽，小撒在學(xué)習(xí)算法
分治法
分治法（divide-and-conquer）是一種算法設(shè)計(jì)策略蜗侈。使用分治法的算法在每一層迭代有3個(gè)步驟：
- 分解（divide）：將原問(wèn)題分解成一系列子問(wèn)題
- 解決（conquer）：遞歸解決子問(wèn)題鲤拿；在子問(wèn)題足夠小時(shí)蚂四，直接解決子問(wèn)題
- 合并（combine）：將子問(wèn)題的結(jié)果合并為原問(wèn)題的解
合并排序
合并排序（merge sort）便是使用了分治的策略沥阳。
如果我們有兩個(gè)已經(jīng)排序好的數(shù)組跨琳，要得到兩者合并后的排序數(shù)組，我們只需反復(fù)比較兩個(gè)數(shù)組頭部（最谢ο）的元素湾宙，將更小的取出并放入結(jié)果數(shù)組：
合并排序圖示
我們可以不斷的將規(guī)模為n的問(wèn)題分解為規(guī)模為n / 2的問(wèn)題，直至n/2 <= 1：
合并排序的時(shí)間復(fù)雜度
遞歸樹(shù)（recursion tree）每向下一層冈绊，規(guī)模為n的問(wèn)題T(n)被分解為兩個(gè)T(n/2)的問(wèn)題侠鳄，因此樹(shù)的總高度為ln(n)/ln(2)。
而合并兩個(gè)T(n/2)死宣，則共需要n次比較并取出較小值伟恶，因此每層的總操作數(shù)為n，由此得到合并排序的時(shí)間復(fù)雜度為θ(n * log(n))毅该。
代碼示例（js）
const merge = (arr, start, mid, end) => {
const arr1 = arr.slice(start, mid + 1)
const arr2 = arr.slice(mid + 1, end + 1)
while (end >= start) {
if (arr2.length === 0) {
arr[start] = arr1.shift()
} else if (arr1[0] < arr2[0]) {
arr[start] = arr1.shift()
} else {
arr[start] = arr2.shift()
}
start++
}
}
const mergeSort = (arr, start, end) => {
if (end > start) {
const mid = Math.floor((end + start) / 2)
mergeSort(arr, start, mid)
mergeSort(arr, mid + 1, end)
merge(arr, start, mid, end)
}
}
小結(jié)
合并排序使用了分治的算法策略博秫，相比插入排序等算法大大提高了時(shí)間復(fù)雜度潦牛，但也引入了O(n)的空間成本。
