分而治之(divide and rule)

分而治之是什么?

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

*它将问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并解决原来的问题—–分,递归,合并

归并排序

*分:吧数组从中间一分二

*解:递归地对两个子数组进行归并排序

*合,合并为有序子数组

快速排序

*分:选基准,按基准把数组分成2个子数组

*解:递归地对两个子数组进行快速排序

*合:对两个子数组进行合并

————————

< strong > what is divide and rule

*Divide and conquer is a method in algorithm design

*It divides the problem into several small problems similar to the original problem, recursively solves the small problem, and then combines the results to solve the original problem —– divide, recursion, merge

< strong > merge sort < / strong >

*Cent: let’s split the array from the middle

*Solution: merge and sort two subarrays recursively

*Merge into ordered subarray

< strong > quick sort < / strong >

*Sub: select the benchmark and divide the array into two sub arrays according to the benchmark

*Solution: quickly sort two subarrays recursively

*Merge: merge two subarrays