排序算法PHP版
文章目录
策略类
定义一系列的策略类,它们独立封装,并且遵循统一的接口
// 抽象策略接口
interface SortStrategy
{
public function sort($arr);
}
冒泡排序
// 具体策略类
class BubbleStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
for ($i = 0; $i < $len - 1 ; $i++) {
$flag = true;
for ($j = 0; $j < $len - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j+1]) {
list($arr[$j], $arr[$j+1]) = array($arr[$j+1], $arr[$j]);
$flag = false;
}
}
if ($flag) {
break;
}
}
return $arr;
}
}
选择排序
class SelectStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$j] < $arr[$minIndex]) {
$minIndex = $j;
}
}
if ($minIndex != $i) {
list($arr[$i], $arr[$minIndex]) = array($arr[$minIndex], $arr[$i]);
}
}
return $arr;
}
}
插入排序
class InsertStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
$nowVal = $arr[$i];
while ($preIndex >= 0 && $arr[$preIndex] > $nowVal) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[++$preIndex] = $nowVal;
}
return $arr;
}
}
希尔排序
注意与插入排序的区别
class ShellStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
$gap = 1;
while($gap < $len / 3) {
$gap = $gap * 3 + 1;
}
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
for ($i = $gap; $i < $len; $i++) {
$preIndex = $i - $gap;
$nowVal = $arr[$i];
while ($preIndex >= 0 && $arr[$preIndex] > $nowVal) {
$arr[$preIndex+$gap] = $arr[$preIndex];
$preIndex -= $gap;
}
$arr[$preIndex+$gap] = $nowVal;
}
}
return $arr;
}
}
归并排序
class MergeStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$mid = floor($len / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
return $this->merge($this->sort($left), $this->sort($right));
}
private function merge($left, $right)
{
$res = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
$res[] = array_shift($left);
} else {
$res[] = array_shift($right);
}
}
while (count($left) > 0) {
$res[] = array_shift($left);
}
while (count($right) > 0) {
$res[] = array_shift($right);
}
return $res;
}
}
快速排序
class QuickStrategy implements SortStrategy
{
public function sort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$mid = $arr[0];
$left = [];
$right = [];
for ($i = 1; $i < $len; $i++) {
if ($arr[$i] > $mid) {
$right[] = $arr[$i];
} else {
$left[] = $arr[$i];
}
}
$left = $this->sort($left);
$right = $this->sort($right);
return array_merge($left, [$mid], $right);
}
}
堆排序
class HeapStrategy implements SortStrategy
{
private $len = 0;
public function sort($arr)
{
$this->len = count($arr);
$this->buildMaxHeap($arr);
for ($i = $this->len - 1; $i > 0; $i--) {
list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);
$this->len--;
$this->heapify($arr, 0);
}
return $arr;
}
public function buildMaxHeap(&$arr)
{
for ($i = floor($this->len/2) - 1; $i >= 0 ; $i--) {
$this->heapify($arr, $i);
}
}
public function heapify(&$arr, $i)
{
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$bigIndex = $i;
if ($left < $this->len && $arr[$left] > $arr[$bigIndex]) {
$bigIndex = $left;
}
if ($right < $this->len && $arr[$right] > $arr[$bigIndex]) {
$bigIndex = $right;
}
if ($bigIndex != $i) {
list($arr[$bigIndex], $arr[$i]) = array($arr[$i], $arr[$bigIndex]);
$this->heapify($arr, $bigIndex);
}
}
}
计数排序
class CountingStrategy implements SortStrategy
{
public function sort($arr)
{
$maxVal = max($arr);
$minVal = min($arr);
for ($i = $minVal; $i <= $maxVal; $i++) {
$bucket[] = 0;
}
foreach ($arr as $v) {
$bucket[$v]++;
}
$newIndex = 0;
while ($newIndex < count($arr)) {
if ($bucket[$minVal] != 0) {
$arr[$newIndex++] = $minVal;
$bucket[$minVal]--;
} else {
$minVal++;
}
}
return $arr;
}
}
环境类
用来管理策略,实现不同策略的切换功能
// 环境角色类
class Role
{
private $sortStrategy;
public function __construct(SortStrategy $sortStrategy)
{
$this->sortStrategy = $sortStrategy;
}
public function asc($array)
{
return $this->sortStrategy->sort($array);
}
}
客户端
通过给予不同的具体策略,获取结果
// 客户端代码
$arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
$role = new Role(new MergeStrategy());
$data = $role->asc($arr);
$role = new Role(new QuickStrategy());
$data = $role->asc($arr);
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论