PHP implements bubble sorting and two-way bubble sorting algorithm_PHP tutorial

Bubble Sort is a relatively simple and stable sorting algorithm. Bubble sorting algorithm steps: Compare adjacent elements. If the first one is larger than the second one, swap their positions; perform the same operation for each pair of adjacent elements. In this way, the final element It is the largest; except for the largest element that has been obtained, repeat the previous steps for the remaining elements until there are no elements that need to be compared, and the sorting is completed. Bubble algorithm, in the best case, the time complexity is O(n); in the worst case, the time complexity is O(n2); the average time complexity is O(n2).

PHP实现冒泡排序、双向冒泡排序算法 1
 
 /**
* Data structure and algorithm (PHP implementation) - Bubble Sort.
*
* @author Chuangxiang Programming (TOPPHP.ORG)
* @copyright Copyright (c) 2013 TOPPHP.ORG All Rights Reserved
* @license http://www.opensource.org/licenses/mit-license.php MIT LICENSE
* @version 1.0.0 - Build20130608
​*/
class BubbleSort {
  /**
* Bubble sort.
*
* @var integer
​*/
  const SORT_NORMAL = 1;
 
  /**
* Bidirectional bubble sort.
*
* @var integer
​*/
  const SORT_DUPLEX = 2;
 
  /**
* The data array that needs to be sorted.
*
* @var array
​*/
  private $data;
 
  /**
* The length of the data array.
*
* @var integer
​*/
  private $size;
 
  /**
* Whether the data array is sorted.
*
* @var boolean
​*/
  private $done;
 
  /**
*Construction method - initialize data.
*
* @param array $data The data array to be sorted.
​*/
  public function __construct(array $data) {
    $this->data = $data;
    $this->size = count($this->data);
    $this->done = FALSE;
  }
 
  /**
* Exchange the positions of two elements in the data array.
*
* @param integer $x The index of the element in the array.
* @param integer $y The index of the element in the array.
​*/
  private function swap($x, $y) {
    $temp = $this->data[$x];
    $this->data[$x] = $this->data[$y];
    $this->data[$y] = $temp;  
  }
 
  /**
* Bubble sort.
​*/
  private function sort() {
    $this->done = TRUE;
 
    for ($i = 1; $i < $this->size; ++$i) {
      // 记录交换数据的次数。
      $swap = 0;
 
      for ($j = $this->size - 1; $j > $i - 1; --$j) {
        if ($this->data[$j] < $this->data[$j - 1]) {
          $this->swap($j - 1, $j);
          ++$swap;
        }
      }
 
      // 若交换数据的次数为0，说明数据数组已有序，不必再进行排序。
      if (0 === $swap) {
        break ;
      }
    }
  }
 
  /**
* Bidirectional bubble sort.
​*/
  private function duplexSort() {
    $this->done = TRUE;
 
    for ($i = 1; $i <= floor($this->size / 2); ++$i) {
      // 记录交换数据的次数。
      $swap = 0;
 
      for ($j = $this->size - 1, $k = $i - 1;
        $j > $i - 1 && $k < $this->size - 1; --$j, ++$k) {
        if ($this->data[$j] < $this->data[$j - 1]) {
          $this->swap($j - 1, $j);
          ++$swap;
        }
 
        if ($this->data[$k] > $this->data[$k + 1]) {
          $this->swap($k, $k + 1);
          ++$swap;
        }
      }
 
// If the number of data exchanges is 0, it means that the data array is in order and there is no need to sort it.
If (0 === $swap) {
         break;
}
}
}

/**
* Get the sorted data array.
*
* @param integer $sort Sorting algorithm: SORT_NORMAL is bubble sort; SORT_DUPLEX is two-way bubble sort.
* @return array Returns the sorted data array.
​*/
public function getResult($sort = self::SORT_NORMAL) {
// If it has been sorted, there is no need to sort again, and the sorted data array will be returned directly.
If ($this->done) {
Return $this->data;
}

switch ($sort) {
case self::SORT_DUPLEX:
           $this->duplexSort();
         break;

case self::SORT_NORMAL:
        default:
$this->sort();
         break;
}

Return $this->data;
}
}
?>

Sample code 1
2
3
4 $bubble = new BubbleSort(array(35, 75, 92, 41, 27, 58));
echo '

', print_r($bubble->getResult(BubbleSort::SORT_DUPLEX), TRUE), '

';
?>

http://www.bkjia.com/PHPjc/477265.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/477265.htmlTechArticleBubble Sort is a relatively simple and stable sorting algorithm. Bubble sorting algorithm steps: Compare adjacent elements. If the first one is larger than the second one, swap them both...