（1）常用排序算法

Class MySort {    /*     * 所有排序均按升序排序     * */    /**     * 插入排序     * @param $arr     * @param $st     * @param $ed     * 通过将元素插入到已排序的序列中不断扩大已排序的序列     */    public function InsertSort(&$arr, $st, $ed) {        for ($i = $st + 1; $i <= $ed; $i++) {            $tmp = $arr[$i];            for ($j = $i - 1; $j >= $st; $j--) {                if ($arr[$j] > $tmp) { // 如果元素比tmp大，就移动元素                    $arr[$j + 1] = $arr[$j];                } else {                    break;                }            }            $arr[$j + 1] = $tmp;        }    }    /**     * 冒泡排序     * @param $arr     * @param $st     * @param $ed     * 通过不断交换相邻元素将更大的元素放在后边，一趟交换之后就能把最大的元素放到最后边，二趟排序可以把次大的元素放在     * 倒数第二的位置，n趟排序就可以把所有元素都放在正确的位置     */    public function BubbleSort(&$arr, $st, $ed) {        for ($i = $ed - 1; $i >= $st; $i--) {            $flag = false;            for ($j = $st; $j <= $i; $j++) {                if ($arr[$j] > $arr[$j + 1]) {                    $tmp = $arr[$j];                    $arr[$j] = $arr[$j + 1];                    $arr[$j + 1] = $tmp;                    $flag = true;                }            }            if (!$flag) { // 优化：如果不发生交换，说明已排好序，退出即可                return;            }        }    }    /**     * 选择排序     * @param $arr     * @param $st     * @param $ed     * 每次选择当前未排序序列最小的元素放在合适的位置，已选择的最小元素构成了已排序序列，不断扩大已排序序列即可实现总体排序     */    public function SelectSort(&$arr, $st, $ed) {        for ($i = $st; $i <= $ed; $i++) {            $min = $i;            for ($j = $i; $j <= $ed; $j++) {                if ($arr[$min] > $arr[$j]) {                    $min = $j;                }            }            if ($min != $i) {                $tmp = $arr[$min];                $arr[$min] = $arr[$i];                $arr[$i] = $tmp;            }        }    }    /**     * 归并排序     * @param $arr     * @param $st     * @param $ed     * 归并排序的关键在于不断合并两个排好序的序列，可以通过递归实现     */    public function MergeSort(&$arr, $st, $ed) {        if ($st < $ed) {            $mid = floor(($st + $ed) / 2); // php数值默认使用float型计算，与Java和C不同，所以此处需要向下取整            $this->MergeSort($arr, $st, $mid);            $this->MergeSort($arr, $mid + 1, $ed);            $this->merge($arr, $st, $mid, $ed);        }    }    /**     * 归并数组arr a1-a2 b1-b2部分     * @param $arr     * @param $a1     * @param $a2     * @param $b1     * @param $b2     */    private function merge(&$arr, $st, $mid, $ed) {        $tmp_arr = array();        $a = $st;        $b = $mid + 1;        while ($a <= $mid && $b <= $ed) {            if ($arr[$a] < $arr[$b]) {                $tmp_arr[] = $arr[$a];                $a++;            }            else {                $tmp_arr[] = $arr[$b];                $b++;            }        }        while ($a <= $mid) {            $tmp_arr[] = $arr[$a];            $a++;        }        while ($b <= $ed) {            $tmp_arr[] = $arr[$b];            $b++;        }        for ($i = $st; $i <= $ed; $i++) {            $arr[$i] = $tmp_arr[$i - $st];        }        echo json_encode(func_get_args()) . "***********" . json_encode($tmp_arr) . "\n";    }    /**     * 快速排序     * @param $arr     * @param $st     * @param $ed     */    public function QuickSort(&$arr, $st, $ed) {        if ($st < $ed) {            $mid = $this->partition($arr, $st, $ed);            $this->QuickSort($arr, $st, $mid - 1);            $this->QuickSort($arr, $mid + 1, $ed);        }    }    /**     * 对数组arr $sd-$ed部分使用轴元素进行划分     * @param $arr     * @param $st     * @param $ed     * @return mixed     */    private function partition(&$arr, $st, $ed) {        $pivot = $arr[$st];        while ($st < $ed) {            while ($st < $ed && $arr[$ed] > $pivot)                $ed--;            $arr[$st] = $arr[$ed];            while ($st < $ed && $arr[$st] <= $pivot)                $st++;            $arr[$ed] = $arr[$st];        }        $arr[$st] = $pivot;        return $st;    }}$sort_obj = new MySort();$arr = [2,9,6,4,0,3,1];$sort_obj->MergeSort($arr, 0, 6);var_dump($arr);

（2）二分查找

Class MyFind {    /**     * 二分查找     * @param $arr     * @param $key     * PS: 必须保证输入的数组arr是升序排列的！     */    public function binarySearch($arr, $key) {        $st = 0;        $ed = count($arr) - 1;        while ($st <= $ed) {            $mid = floor(($st + $ed) / 2);            if ($key == $arr[$mid]) {                return $mid;            }            elseif ($key < $arr[$mid]) {                $ed = $mid - 1;            }            else {                $st = $mid + 1;            }        }        return -1;    }    /**     * 使用递归实现二分查找     * @param $arr     * @param $key     */    public function binarySearchWithRecursion($arr, $key) {        return $this->recursion($arr, $key, 0, count($arr) - 1);    }    private function recursion($arr, $key, $st, $ed) {        if ($st > $ed) {            return -1;        }        $mid = floor(($st + $ed) / 2);        if ($key == $arr[$mid]) {            return $mid;        }        elseif ($key < $arr[$mid]) {            return $this->recursion($arr, $key, $st, $mid - 1);        }        else {            return $this->recursion($arr, $key, $mid + 1, $ed);        }    }    /**     * 二叉搜索树查找     * @param $root     * @param $key     * 二叉树结点定义：     * class ListNode {     *  public $left;     *  public $right;     *  public $value;     * }     */    public function binaryTreeSearch($root, $key) {        while ($root != null) {            if ($key == $root->value) {                return $root;            }            elseif ($key < $root->value) {                $root = $root->left;            }            else {                $root = $root->right;            }        }        return null;    }    /**     * 二分查找不小于$key的最小数（很多算法会用到，比如一致性哈希算法）     * @param $arr     * @param $key     * 进行二分查找时，最后查找的位置总是最接近key的位置，如果key不存在，则最后查找的位置一定是小于key的最大数或者大于key的最小数     */    public function binarySearchMinSupper($arr, $key) {        $st = 0;        $ed = count($arr) - 1;        while ($st <= $ed) {            $mid = floor(($st + $ed) / 2);            if ($key == $arr[$mid]) {                return $arr[$mid];            }            elseif ($key < $arr[$mid]) {                $ed = $mid - 1;            }            else {                $st = $mid + 1;            }        }        return $key > $arr[$mid] ? $arr[$mid + 1] : $arr[$mid]; // 此处数组可能越界

}}$find_obj = new MyFind();$arr = [0,1,2,3,4,6,9];$a = $find_obj->binarySearchMinSupper($arr, 2.1);var_dump($a);

 （3）栈与队列（顺序栈、链式栈、顺序队列、链式队列）

abstract Class MyStack {    protected $capacity = -1;    public function __construct($capacity = null) {        if (isset($capacity)) {            $this->capacity = $capacity;        }    }    abstract public function push($val);    abstract public function top();    abstract public function pop();    abstract public function isEmpty();    abstract public function isFull();}Class MyArrayStack extends MyStack { //顺序栈    protected $arr = array();    public function push($val) {        if ($this->isFull()) {            return false;        }        $this->arr[] = $val;        return true;    }    public function top() {        return !$this->isEmpty() ? end($this->arr) : null;    }    public function pop() {        return !$this->isEmpty() ? array_pop($this->arr) : null;    }    public function isEmpty() {        return count($this->arr) == 0;    }    public function isFull() {        if ($this->capacity == -1) {            return false;        }        return count($this->arr) == $this->capacity;    }}Class MyLinkedStackNode {    public $val;    public $next;}Class MyLinkedStack { //链式栈    protected $pointer = null;    protected $count = 0;    public function push($val) {        if ($this->isFull()) {            return false;        }        $node = new MyLinkedStackNode();        $node->val = $val;        $node->next = $this->pointer;        $this->pointer = $node;        $this->count++;        return true;    }    public function top() {        return !$this->isEmpty() ? $this->pointer->val : null;    }    public function pop() {        if ($this->isEmpty()) {            return null;        }        $val = $this->pointer->val;        $this->pointer = $this->pointer->next;        $this->count--;        return $val;    }    public function isEmpty() {        return $this->count == 0;    }    public function isFull() {        if ($this->capacity == -1) {            return false;        }        return $this->count == $this->capacity;    }}abstract Class MyQueue {    protected $capacity = -1;    public function __construct($capacity = null) {        if (isset($capacity)) {            $this->capacity = $capacity;        }    }    abstract public function enqueue($val);    abstract public function front();    abstract public function dequeue();    abstract public function isEmpty();    abstract public function isFull();}Class MyArrayQueue extends MyQueue {    protected $arr = array();    public function enqueue($val)    {        if ($this->isFull()) {            return false;        }        $this->arr[] = $val;        return true;    }    public function front()    {        return !$this->isEmpty() ? $this->arr[0] : null;    }    public function dequeue()    {        return !$this->isEmpty() ? array_shift($this->arr) : null;    }    public function isEmpty()    {        return count($this->arr) == 0;    }    public function isFull()    {        return count($this->arr) == $this->capacity;    }}Class MyLinkedQueueNode {    public $val;    public $next;}Class MyLinkedQueue extends MyQueue {    protected $head = null, $tail = null;    protected $count = 0;    public function enqueue($val)    {        if ($this->isFull()) {            return false;        }        $node = new MyLinkedQueueNode();        $node->val = $val;        if ($this->head == null) { //如果队列为空，效果等同于$this->isEmpty()            $this->head = $this->tail = $node;        } else {            $this->tail->next = $node;            $this->tail = $this->tail->next;        }        return true;    }    public function front()    {        return !$this->isEmpty() ? $this->head->val : null;    }    public function dequeue()    {        if ($this->isEmpty()) {            return null;        }        $val = $this->head->val;        if ($this->head == $this->tail) { //如果只有一个元素            $this->head = $this->tail = null;        }        else {            $this->head = $this->head->next;        }        $this->count--;        return $val;    }    public function isEmpty()    {        return $this->count == 0;    }    public function isFull()    {        return $this->count == $this->capacity;    }}