快速排序

Posted on Posted in php
Tips: 本文创建于2014年4月10日,已超过 2 年,内容或图片可能已经失效!

类::工具

[code lang="php"]
class sort {
public $list;
public $start;
public $end;
public function __construct($list) {
$this->list = $list;
$this->start = 0;
$this->end = count ( $list ) - 1;

$this->quickSort ( $this->list, $this->start, $this->end );
}
public function quickSort(&$list, $start, $end) {
// 判断是否需要排序
if ($start < $end) {
// 选取参考元,选最后一个
$last_value = $list [$end];
// 设置了两个指示器(两个下标记录变量),将其初始化到序列中第一元素,与倒数第二个元素上
$i = $start;
$j = $end - 1;
// 移动指示器
while ( true ) {
while ( $i < $end && $list [$i] < $last_value ) {
++ $i; // 移动$i,别越界
}
while ( $j >= $start && $list [$j] > $last_value ) {
-- $j; // 移动$j,别越界
}
if ($j < $i) {
break; // 终止
}
// 交换
$this->swap($list [$i], $list [$j]);
// 移动指示器
++ $i;
-- $j;
}// 移动结束
// 交换参考元与$i所指向的元素的值
$this->swap($list [$i], $list [$end]);
// 此时,对$start到$j, 与 $i+1到$end分别做递归快速排序
$this->quickSort ( $list, $start, $j ); // 小于部分排序
$this->quickSort ( $list, $i + 1, $end ); // 大于部分排序
}

}
public function swap(&$a,&$b){
$tmp = $a;
$a = $b;
$b = $tmp;
}
}
[/code]

使用

[code lang="php"]
$list = array (
999,
70,
40,
60,
90,
30,
80,
50
);
$e = new sort($list);
var_export($e);
[/code]

显示

[code lang="php"]
sort::__set_state(array( 'list' => array ( 0 => 30, 1 => 40, 2 => 50, 3 => 60, 4 => 70, 5 => 80, 6 => 90, 7 => 999, ), 'start' => 0, 'end' => 7, ))
[/code]

» 转载请注明来源:若我若鱼 » 快速排序

Leave a Reply

Your email address will not be published. Required fields are marked *

nineteen − 4 =