分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决,小的子问题解决了,大问题也就解决了。
一、概念
- 给定一个待排序数组,先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。
- 归并排序使用的就是分治思想。
- 分治算法一般都是用递归来实现的
- 分治是一种解决问题的处理思想,递归是一种编程技巧,两者并不冲突
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| function mergeSort($data) { $len = count($data); if ($len <=1) { return $data; }
$middle = intval($len/2); $left = mergeSort(array_slice($data, 0, $middle)); $right = mergeSort(array_slice($data, $middle)); $data = mergeArr($left, $right); // $data = mergeArr1($left, $right); return $data; }
function mergeArr($arr1, $arr2) { $result = []; // 合并两个数组的算法NB while (count($arr1) && count($arr2)) { $result[] = $arr1[0] < $arr2[0] ? array_shift($arr1) : array_shift($arr2); } return array_merge($result, $arr1, $arr2); }
function mergeArr1($arr1, $arr2) { $i = 0; $j = 0; $result = array(); $len1 = count($arr1); $len2 = count($arr2);
while ($i < $len1 && $j < $len2) { if ($arr1[$i] < $arr2[$j]) { $result[] = $arr1[$i]; $i++; } else { $result[] = $arr2[$j]; $j++; } }
while ($i < $len1) { // $result[] = $arr1[$i++]; $result[] = $arr1[$i]; $i++; }
while ($j < $len2) { // $result[] = $arr2[$j++]; $result[] = $arr2[$j]; $j++; }
return $result; }
|