首页 > 代码库 > PHP 几个算法

PHP 几个算法

一 ,排序

1,冒泡法

冒泡法的核心思想是两两比较,如果大小颠倒就置换。冒泡法的时间复杂度是O(n*n)

function maopao_sort($arr){
  $len = count($arr);
  for($i=0;$i<$len;$i++){
    for($j=0;$j<$len-$i-1;$j++){
      if($arr[$j]>$arr[$j+1]){
        $temp = $arr[$j];
        $arr[$j] = $arr[$j+1];
        $arr[$j+1] = $temp;
      }
    }
  }
  return $arr;
}

2,快速排序法

快速排序法的思想是将待排序的数分成两组,左边都小于右边,然后递归,快速排序的平均运行时间为θ(nlogn)

function quick_sort($arr){
  $len = count($arr);
  if($len<=1){
    return $arr;
  }else{
    $key = $arr[0];
    $left = array();
    $right = array();
    for($i=1;$i<$len;$i++){
      if($key>=$arr[$i]){
        $left[]=$arr[$i];
      }else{
        $right[]=$arr[$i];
      }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left,array($key),$right);
  }

}

3,选择排序法

简单选择排序的基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

function select_sort($arr){
  $len = count($arr);
  for($i=0;$i<$len;$i++){
    for($j=$i+1;$j<$len;$j++){
      if($arr[$i]>$arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
  return $arr;
}

4,插入排序法

插入排序法的核心思想是,假设第一个数已经排好序,从第二个数开始,从后向前扫面已经排好的序列,找到合适的位置,插入。后面的数全部后移。

function insert_sort($arr){
  $len = count($arr);
  for($i=1;$i<$len;$i++){
    $temp = $arr[$i];
    $j = $i-1;
    while($j>=0 && $arr[$j]>$temp){
      $arr[$j+1]=$arr[$j];
      $arr[$j] = $temp;
      $j--;
    }
  }
  return $arr;
}

 

PHP 几个算法