归并算法

概述

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

PHP 实现(递归方法)

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 实现(递归法)

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)
}

黄铭博客
请先登录后发表评论
  • latest comments
  • 总共0条评论