Explication détaillée de plusieurs exemples d'algorithmes de tri en PHP

Implémentation PHP de quatre algorithmes de tri :

1) L'idée de base du tri par insertion (Insertion Sort) est la suivante :
Chaque fois qu'un enregistrement à trier est trié selon sa taille, le mot clé est inséré à la position appropriée dans le sous-fichier précédemment trié jusqu'à ce que tous les enregistrements soient insérés.

2) L'idée de base du tri par sélection est la suivante : À chaque passage, l'enregistrement avec le plus petit mot-clé est sélectionné parmi les enregistrements à trier, et l'ordre est placé dans le enregistrement trié. À la fin du sous-fichier trié, jusqu'à ce que tous les enregistrements soient triés.

3)

L'idée de base du tri à bulles est : Comparez les mots-clés des enregistrements à trier par paire, et lorsqu'il s'avère que l'ordre des deux enregistrements est opposé, ils seront échangés jusqu'à ce qu'il n'y ait plus d'inversion jusqu'à ce que la séquence soit enregistrée.

4) Le tri rapide est essentiellement le même que le tri à bulles et est une application du tri par échange. L’idée de base est donc la même que celle du tri à bulles ci-dessus.

1. Le fichier sort.php est le suivant :

<?php
class Sort {
  private $arr  = array(); 
  private $sort  = &#39;insert&#39;;
  private $marker = &#39;_sort&#39;;
  private $debug = TRUE;
  /**
   * 构造函数
   *
   * @param  array  例如：
   $config = array (
   &#39;arr&#39; => array(22,3,41,18) , //需要排序的数组值
   &#39;sort&#39; => &#39;insert&#39;, //可能值: insert, select, bubble, quick
   &#39;debug&#39; => TRUE //可能值: TRUE, FALSE
   )
   */
  public function construct($config = array()) {
    if ( count($config) > 0) {
      $this->_init($config);
    }
  }
  /**
   * 获取排序结果
   */
  public function display() {
    return $this->arr;
  }
  /**
   * 初始化
   *
   * @param  array
   * @return bool
   */
  private function _init($config = array()) {
    //参数判断
    if ( !is_array($config) OR count($config) == 0) {
      if ($this->debug === TRUE) {
        $this->_log("sort_init_param_invaild");
      }
      return FALSE;
    }
    //初始化成员变量
    foreach ($config as $key => $val) {
      if ( isset($this->$key)) {
        $this->$key = $val;
      }
    }
    //调用相应的成员方法完成排序
    $method = $this->sort . $this->marker;
    if ( ! method_exists($this, $method)) {
      if ($this->debug === TRUE) {
        $this->_log("sort_method_invaild");
      }
      return FALSE;
    }
    if ( FALSE === ($this->arr = $this->$method($this->arr)))
      return FALSE;
    return TRUE;
  }
  /**
   * 插入排序
   * 
   * @param  array
   * @return bool
   */
  private function insert_sort($arr) {
    //参数判断
    if ( ! is_array($arr) OR count($arr) == 0) {
      if ($this->debug === TRUE) {
        $this->_log("sort_array(insert)_invaild");
      }
      return FALSE;
    }
    //具体实现
    $count = count($arr);
    for ($i = 1; $i < $count; $i++) {
      $tmp = $arr[$i];
      for($j = $i-1; $j >= 0; $j--) { 
        if($arr[$j] > $tmp) {
          $arr[$j+1] = $arr[$j];
          $arr[$j] = $tmp;
        }
      }
    }
    return $arr;
  }
  /**
   * 选择排序
   * 
   * @param  array
   * @return bool
   */
  private function select_sort($arr) {
    //参数判断
    if ( ! is_array($arr) OR count($arr) == 0) {
      if ($this->debug === TRUE) {
        $this->_log("sort_array(select)_invaild");
      }
      return FALSE;
    }
    //具体实现
    $count = count($arr);
    for ($i = 0; $i < $count-1; $i++) {
      $min = $i;
      for ($j = $i+1; $j < $count; $j++) {
        if ($arr[$min] > $arr[$j]) $min = $j;
      }
      if ($min != $i) {
        $tmp = $arr[$min];
        $arr[$min] = $arr[$i];
        $arr[$i] = $tmp;
      }
    }
    return $arr;
  }
  /**
   * 冒泡排序
   * 
   * @param  array
   * @return bool
   */
  private function bubble_sort($arr) {
    //参数判断
    if ( ! is_array($arr) OR count($arr) == 0) {
      if ($this->debug === TRUE) {
        $this->_log("sort_array(bubble)_invaild");
      }
      return FALSE;
    }
    //具体实现
    $count = count($arr);
    for ($i = 0; $i < $count; $i++) {
      for ($j = $count-1; $j > $i; $j--) {
        if ($arr[$j] < $arr[$j-1]) {
          $tmp = $arr[$j];
          $arr[$j] = $arr[$j-1];
          $arr[$j-1] = $tmp;
        }
      }
    }
    return $arr;  
  }
  /**
   * 快速排序
   * 
   * @param  array
   * @return bool
   */
  private function quick_sort($arr) {
    //具体实现
    if (count($arr) <= 1) return $arr; 
    $key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < count($arr); $i++){
      if ($arr[$i] <= $key)
        $left_arr[] = $arr[$i];
      else
        $right_arr[] = $arr[$i];
    }
    $left_arr = $this->quick_sort($left_arr);
    $right_arr = $this->quick_sort($right_arr); 
 
    return array_merge($left_arr, array($key), $right_arr);
  }
  /**
   * 日志记录
   */
  private function _log($msg) {
    $msg = &#39;date[&#39; . date(&#39;Y-m-d H:i:s&#39;) . &#39;] &#39; . $msg . &#39;\n&#39;;
    return @file_put_contents(&#39;sort_err.log&#39;, $msg, FILE_APPEND);
  }
}
/*End of file sort.php*/
/*Location htdocs/sort.php */

2. Le fichier sort_demo.php est le suivant :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!