[php算法]查找和排序

<?php

/*
 * php常用算法集合
 * 
 */

//格式化输出
function dump($obj) {
    echo '<pre>';
    print_r($obj);
    echo '</pre>';
}

//交换数据
function swap(&$a, &$b) {
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

//快速排序
function quick_sort($a) {
    if (count($a) <= 1) {
        return $a;
    }
    $l = array();
    $r = array();
    $x = $a[0];
    $c = count($a);
    for ($i = 1; $i < $c; $i++) {
        if ($a[$i] <= $x) {
            $l[] = $a[$i];
        } else {
            $r[] = $a[$i];
        }
    }
    $l = quick_sort($l);
    $r = quick_sort($r);
    return array_merge($l, array($x), $r);
}

//选择排序
function select_sort($a) {
    $n = count($a);
    for ($i = 0; $i < $n; $i++) {
        $min = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($a[$j] < $a[$min]) {
                $min = $j;
            }
        }
        swap($a[$i], $a[$min]);
    }
    return $a;
}

//插入排序
function insert_sort($a) {
    $n = count($a);
    for ($i = 1; $i < $n; $i++) {
        if ($a[$i] < $a[$i - 1]) {
            $temp = $a[$i];
            for ($j = $i - 1; (($j >= 0) && $a[$j] > $temp); $j--) {
                $a[$j + 1] = $a[$j];
            }
            $a[$j + 1] = $temp;
        }
    }
    return $a;
}

//冒泡排序
function bubble_sort($a) {
    $n = count($a);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i; $j < $n; $j++) {
            if ($a[$i] > $a[$j]) {
                swap($a[$i], $a[$j]);
            }
        }
    }
    return $a;
}

//希尔排序
function shell_sort($a) {
    $n = count($a);
    for ($gap = $n / 2; $gap > 0; $gap = intval($gap / 2)) {
        for ($i = $gap; $i < $n; $i++) { //从gap开始,  
            if ($a[$i] < $a[$i - $gap]) { //从$gap开始，每个元素与自己组内的数据进行直接插入排序    
                $temp = $a[$i];
                for ($k = $i - $gap; ($k >= 0 && $a[$k] > $temp); $k-=$gap) {
                    $a[$k + $gap] = $a[$k];
                }
                $a[$k + $gap] = $temp;
            }
        }
    }
    return $a;
}

//顺序查找
function sequential_search($a, $finded) {
    $length = count($a);
    for ($i = 0; $i < $length; $i++) {
        if ($a[$i] == $finded) {
            return $i;
        }
    }
    return -1;
}

//折半查找 || 二分查找
function half_search($a, $low, $hight, $finded) {
    while ($low <= $hight) {
        $middle = intval(($low + $hight) / 2);
        if ($a[$middle] == $finded) {
            return $middle;
        } else if ($a[$middle] < $finded) {
            $low = $middle + 1;
        } else if ($a[$middle] > $finded) {
            $hight = $middle - 1;
        }
    }
    return -1;
}

//排列组合
class Permutation {

    var $srcList;       //存放原始数列数组
    var $rstList;       //存放最终数列数组
    var $srcLen;        //原始数列的长度
    var $rstLen;        //结果数列的长度
    var $rstOrder;      //求排列或组合标志

    function Permutation($m) {
        if (!is_array($m)) {
            echo "参数类型错误：Permutation(array $m) $m为数组类型";
            return false;
        }
        $this->srcLen = count($m);
        $this->srcList = $m;
    }

    //取得排列组合结果, $order=1为取排列,$order=2为取组合
    function getList($n, $order = 1) {
        if (!is_int($n)) {
            echo "参数类型错误：getList(int $n) $n为整数类型";
            return false;
        }
        if ($n > $this->srcLen) {
            echo "要求的排列组合的长度不能大于原始数列的长度";
            return false;
        }
        $this->rstLen = $n;
        $this->rstOrder = $order;
        $this->rstList = array();
        $this->doPermutation($this->srcList, $this->rstLen);
        return $this->rstList;
    }

    //递归计算从m中取n的排列, $rst存取出的排列
    function doPermutation($m, $n, &$rst = array()) {
        //如果已经取完
        if ($n == 0) {
            $this->rstList[] = $rst;
            $rst = array();
            return true;
        }
        //从当前数列m中选取一个值，并更新数列m
        foreach ($m as $key => $value) {
            $nextM = $m;
            //判断是取排列还是组合
            switch ($this->rstOrder) {
                //取排列, 清空当前取出的值
                case 1: unset($nextM[$key]);
                    break;
                //取组合, 清空当前及前面所取的值
                case 2: array_splice($nextM, 0, $key + 1);
                    break;
                default:unset($nextM[$key]);
                    break;
            }
            $nextRst = $rst;
            //将取的值放到结果数列中
            $nextRst[] = $value;
            $this->doPermutation($nextM, $n - 1, $nextRst);
        }
    }

}

$m = array(0, 1, 2, 3, 4, 5);
$p = new Permutation($m);
$arr = $p->getList(3, 1);
foreach ($arr as $value) {
    echo implode(",", $value) . "<br>";
}