前端之算法（六）分而治之

大家好，前面几章我们说了很多的像链表，集合，字典等数据结构，也说了很多的排序和搜索算法，今天我们要聊的是分而治之这种方法，它既不是数据结构，也不是算法，你可以把它当作一种思想，解决问题的一种思路。

分而治之

• 分而治之是算法设计中的一种方法。

• 它将一个问题分成多个和原问题相似的小问题。

• 递归解决小问题，再将结果合并已解决原来的问题。

• 上面的三个步骤就是分而治之的通用步骤，所有的分而治之思路都是这三个步骤。

场景一：归并排序

归并排序就是我们之前聊到的一种算法，这种算法就是利用分而治之这种思路来设计的。

• 分：把数组从中间一分为二。

• 解：递归地对两个子数组进行归并排序。

• 合：合并有序子数组。

场景二：快速排序

快速排序中也运用了分而治之这种思想。

• 分：选基准，按基准把数组分成两个子数组。

• 解: 递归地对两个子数组进行快速排序，然后在对子数组继续进行分,直到分成长度为 1 地数组，这时候递归就结束了。

• 合：最后就是合并，先把数组长度为 1 地进行合并，在对两个合并好的数组进行合并，直到所有数组合并成一个数组。

总结

我们可以看出上面两种场景，这不就是一个分而治之吗？先把一个大问题，分成很多个小问题，在把小问题解决，在合并解决大问题，所以这两种排序算法就是对分而治之思想地典型应用。

End~~