归并算法

发表于2021-12-15更新于2021-12-18

概述

归并算法采用分治法:
1: 把长度为 n 的 array 分成两半。
3: 把左半边 array 及右半边 array 分别以 Merge Sort 进行 sorting。 (recursive)
3: merge 左半边及右半边 sorted array。

PHP 实现（递归方法）

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
function mergeSort(array $array):array
{
	$count = count($array);
	if($count < 2){
		return $array;
	}

	$left = $right = [];
	$middle = round($count / 2);

	$left = array_slice($array, 0, $middle);
	$right = array_slice($array, $middle);

	$leftArray = mergeSort($left);
	$rightArray = mergeSort($right);

	return merge($leftArray, $rightArray);
}

function merge(array $leftArray, array $rightArray):array
{
	$tempArray = [];
	while (count($left) > 0 && count($right) > 0) {
		if($left[0] < $right[0]){
			$tempArray[] = array_shift($left);
		} else {
			$tempArray[] = array_shift($right);
		}
	}

	return array_merge($tempArray, $left, $right);
}


var_export(mergeSort([12, 34, 3, 2, 67, 21, 1, 56]));

JavaScript 实现（递归法）

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
function memgeSort(array){
  var left = [], right = [], leftArray = [], rightArray = [];
  var len = array.length
  if(len < 2){
     return array
  }
  
  var middle = parseInt(len / 2)
  left = array.slice(0, middle)
  right = array.slice(middle)

  leftArray = memgeSort(left)
  rightArray = memgeSort(right)
  
  return sort(left, right)
}

function sort(left, right){
  var res = [];
 
  while(left.length > 0 && right.length > 0 ){
        if(left[0] < right[0]){
          res.push(left.shift())
        } else {
          res.push(right.shift())
        }
  }
  
  return res.concat(left, right)
}