数据结构与算法基础

树

二叉树

一棵二叉树（binary tree）是结点的一个有限集合，该集合或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

二叉树的特点
1. 在二叉树的第i层上至多有$2^{i-1}$个结点（i≥1）
2. 深度为k的二叉树至多有$2^{k-1}$个结点（k≥1）
二叉树遍历
1. 先（根）序遍历:若二叉树为空，则空操作；否则访问根结点->先序遍历左子树->先序遍历右子树。
2. 中（根）序遍历:若二叉树为空，则空操作；否则中序遍历左子树->访问根结点->中序遍历右子树。
3. 后（根）序遍历:若二叉树为空，则空操作；否则后序遍历左子树->后序遍历右子树->访问根结点
遍历算法
1. 递归遍历
2. 栈实现的非递归遍历:中序遍历非递归遍历① 初始化一个空栈S，指针p指向根结点。② 申请一个结点空间q，用来存放栈顶弹出的元素。③ 当p非空或者栈S非空时，循环执行以下操作：如果p非空，则将p进栈，p指向该结点的左孩子；如果p为空，则弹出栈顶元素并访问，将p指向该结点的右孩子。

线性表查找

顺序查找

顺序查找（Sequential Search）的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。
时间复杂度 O(n)

折半查找

从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。
时间复杂度 O ($\log_2{n}$)

public function binarySearch($arr, $target)
{
    if (empty($arr)) {
        return false;
    }
    $left = 0;
    $right = count($arr);
    while ($left <= $right) {
        $mid = ceil(($left + $right) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } else if ($arr[$mid] > $target) {
            $right = $mid - 1;
        } else {
            $left = $mid + 1;
        }
    }
}

线性表排序

插入排序-快速插入排序

算法:将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

 public function insertSort($arr)
    {
        if (empty($arr)) {
            return $arr;
        }
        $count = count($arr);
        for ($i = 1; $i < $count; $i++) {
            if ($arr[$i] < $arr[$i - 1]) {
                $x = $arr[$i];//哨兵
                $arr[$i] = $arr[$i - 1];
                for ($j = $i - 1; isset($arr[$j]) && $x < $arr[$j]; $j--) {
                    $arr[$j + 1] = $arr[$j];
                }
                $arr[$j + 1] = $x;
            }
        }
        return $arr;
    }

时间复杂度:O($n^2$) 空间复杂度:O(1)

插入排序-希尔排序

选择排序

设待排序的记录存放在数组r[1…n]中。第一趟从r[1]开始，通过n−1次比较，从n个记录中选出关键字最小的记录，记为r[k]，交换r[1]和r[k]。
第二趟从r[2]开始，通过n−2次比较，从n−1个记录中选出关键字最小的记录，记为r[k]，交换r[2]和r[k]。
依次类推，第i趟从r[i]开始，通过n−i次比较，从n−i+1个记录中选出关键字最小的记录，记为r[k]，交换r[i]和r[k]。
经过n−1趟，排序完成。

    public function selectSort($arr)
    {
        if (empty($arr)) {
            return $arr;
        }
        $count = count($arr);
        for ($i = 0; $i < $count; $i++) {
            $k = $i;
            //K 指向此次排序最小的
            for ($j = $i + 1; $j < $count; $j++) {
                if ($arr[$j] < $arr[$k]) {
                    $k = $j;
                }
            }
            //交换
            if ($k != $i) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $temp;
            }
        }
        return $arr;
    }

时间复杂度:O($n^2$)
空间复杂度:O(1)

冒泡排序

设待排序的记录存放在数组r[1…n]中。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1].key>L.r[2].key），则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直至第n−1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。
然后进行第二趟起泡排序，对前n−1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n−1个记录的位置上。
重复上述比较和交换过程，第i趟是从L.r[1]到L.r[n−i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n−i+1个记录中关键字最大的记录被交换到第n−i+1的位置上。直到在某一趟排序过程中没有进行过交换记录的操作，说明序列已全部达到排序要求，则完成排序。

 //交换排序-冒泡排序
    public function bubbleSort($arr)
    {
        if (empty($arr)) {
            return $arr;
        }
        $count = count($arr);
        for ($i = 0; $i < $count; $i++) {
            for ($j = 0; $j < $count - 1; $j++) {
                if ($arr[$j + 1] < $arr[$j]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j + 1];
                    $arr[$j + 1] = $temp;
                }
            }
        }
        return $arr;
    }
    //交换排序-冒泡排序
    public function bubbleSort1($arr) {
        if (empty($arr)) {
            return $arr;
        }
        $count = count($arr);
        $m = $count - 1;
        $flag = 1;
        while ($m > 0 && $flag == 1) {
            $flag = 0;
            for ($j = 1; $j < $m; $j++) {
                if ($arr[$j + 1] < $arr[$j]) {
                    $flag = 1;
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j + 1];
                    $arr[$j + 1] = $temp;
                }
            }
            $m--;
        }
        return $arr;
    }

时间复杂度:O($n^2$)
空间复杂度:O(1)

快速排序

在待排序的n个记录中任取一个记录（通常取第一个记录）作为枢轴（或支点），设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换到前面，把所有关键字大于pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢轴放置在分界处的位置。然后，分别对左、右子表重复上述过程，直至每一子表只有一个记录时，排序完成。

    public function swap($x, $y)
    {
        $temp = $this->sort_arr[$x];
        $this->sort_arr[$x] = $this->sort_arr[$y];
        $this->sort_arr[$y] = $temp;
    }

    public function quickSortRecursive($low, $high)
    {
        if ($low >= $high) {
            return;
        }
        $pivotkey = $this->sort_arr[$high];
        $left = $low; $right = $high - 1;
        while ($left < $right) {
            while ($left < $right && $this->sort_arr[$left] <= $pivotkey) {
                $left++;
            }
            while ($left < $right && $this->sort_arr[$right] >= $pivotkey) {
                $right--;
            }
            $this->swap($left, $right);
        }
        if ($this->sort_arr[$left] >= $this->sort_arr[$high]) {
            $this->swap($left, $high);
        } else {
            $left++;
        }
        $this->quickSortRecursive($low, $left - 1);
        $this->quickSortRecursive($left + 1, $high);
    }

时间复杂度:最差O($n^2$)，平均O(n$\log_2{n}$)
空间复杂度:快速排序是递归的，执行时需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致，所以最好情况下的空间复杂度为O($\log_2{n}$)，最坏情况下为O(n)。

归并排序

计数排序

计数排序的逻辑：

找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

    /**
     * 计数排序
     */
    public function countSort($arr, $max_value = 200)
    {
        if (empty($arr)) {
            return $arr;
        }
        $frequency = new SplFixedArray($max_value + 1);
        foreach ($arr as $key => $value) {
            if (!isset($frequency[$value])) {
                $frequency[$value] = 0;
            }
            $frequency[$value] += 1;
        }
        $return = [];
        for ($i = 0; $i < count($frequency); $i++) {
            if ($frequency[$i] > 0) {
                for ($j = 0; $j < $frequency[$i]; $j++) {
                    $return[] = $i;
                }
            }
        }
        return $return;
    }

时间复杂度:O(n + k)
空间复杂度:O(n + k)

文章目录