常见算法

发表于 | 分类于 ， ， | 阅读次数:

文章参考：todayqq/PHPerInterviewGuide

常用的排序算法的时间复杂度和空间复杂度

排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 O(n^2) O(n^2) 稳定 O(1)
快速排序 O(n^2) O(n*logn) 不稳定 O(logn)~O(n)
选择排序 O(n^2) O(n^2) 稳定 O(1)
二叉树排序 O(n^2) O(n*logn) 不一顶 O(n)
插入排序 O(n^2) O(n^2) 稳定 O(1)
堆排序 O(n*logn) O(n*logn) 不稳定 O(1)
希尔排序 O O 不稳定 O(1)

冒泡排序

插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是O(n^2)，最好情况下都是O(n)，空间复杂度是O(1)

  • 原理:比较相邻两个元素,如果前一个元素大于后一个元素则向后移,然后跟后边元素依次比较直到最大值冒泡到最后一个元素
  • 结论:假设数组长度为n,则共经过N=n-1轮排序,每轮进行N-i次比较,我们可以使用双层循环语句,外层循环控制轮次,内层循环控制比较次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubble_sort($arr) {
    $count = count($arr);
    for($i=0; $i < $count-1; $i++) {
        for($j=0; $j < $count-1-$i; $j++) {
            if($arr[$j] > $arr[$j+1]) {//倒序排只需把大于号换成小于号即可
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}
print_r(bubble_sort([6, 3, 8, 2, 9, 1, 2]));

运行结果:

1
2
3
4
5
6
7
8
9
10
Array
(
    [0] => 1
    [1] => 2
    [2] => 2
    [3] => 3
    [4] => 6
    [5] => 8
    [6] => 9
)

参考: PHP 冒泡排序

快速排序

快速排序是对冒泡排序的一种改进，不稳定，平均时间复杂度：O(nlogn)

实现

  • 原理: 选择一个基准数(一般为第一个元素),新建两个空数组,遍历整个数组元素,如果数组元素比基准数小,则放到left数组,如果大于基准数则放到right数组,然后在对新数组递归进行相同的操作
  • 基准数: 第一个元素
  • 递归点: 新构造的数组个数大于1则继续进行拆分排序
  • 递归出口: 数组个数小于等于1或非数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quick_sort($arr) {
    $count = count($arr);
    if($count <= 1) {
        return $arr;
    }
    $base = $arr[0];
    $left = $right = array();
    for($i=1; $i < $count; $i++) {
        if($arr[$i] < $base) { //倒序排只需把符号换成大于号即可
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left, array($base), $right);
}

$arr = [6,3,8,6,4,4,2,9,5,1];
print_r(quick_sort($arr));

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 6
    [8] => 8
    [9] => 9
)

参考： php实现快速排序

复杂度证明

最优情况

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断
推导如下：

1
2
3
4
5
T（n）≤2T（n/2） +n，T（1）=0  
T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n  
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n  
……  
T（n）≤nT（1）+（log2n）×n= O(nlogn)

在最优的情况下，快速排序算法的时间复杂度为O(nlogn).

最坏情况

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录
也就是枢轴的位置，因此比较次数为 ，最终其时间复杂度为O(n^2)。

平均情况

平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：

由数学归纳法可证明，其数量级为O(nlogn)。

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

参考：9.9.2 快速排序复杂度分析

二分查找（折半查找）

时间复杂度：O(log2n)以2为底n的对数

实现

  • 需求: 提供一个有序数组和一个目标数字,找出该数字在有序数组中的位置
  • 原理：
  1. 知道起始位置和结束位置(默认为数组起点和终点索引值), 取数组中间位置数字与目标数字比较.
  2. 如果目标值小于中间值,则目标值在中间位置之前,此时再次二分，起始位置不变,结束位置变更为中间位置-1.
  3. 如果中间值小于目标值,则目标值在中间位置之后,此时再次二分，起始位置为中间位置+1,结束位置不变.
  4. 如果中间值等于目标值则返回中间位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function binary_search($target, $arr) {
    $low = 0;
    $high = count($arr) -1;
    while($low <= $high) { //<=兼容target = 1情况
        $mid = floor(($low+$high) / 2);
        //var_dump($low.'_'.$high.'_'.$mid);//打印比较过程
        if($target < $arr[$mid]) {
            $high = $mid -1;
        }
        if($target > $arr[$mid]) {
            $low = $mid +1;
        }
        if($target == $arr[$mid]) {
            return $mid;
        }
    }
    //var_dump($low.'_'.$high.'_'.$mid);//打印比较过程
    return false;
}
$target = 7;//分别测试target=1,2,7
$arr = [1, 2, 3, 6, 8, 9, 10, 13, 14];//共9个数字
var_dump($target);
print_r($arr);
$ret = binary_search($target, $arr);
var_dump($ret);

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int(7)
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 6
    [4] => 8
    [5] => 9
    [6] => 10
    [7] => 13
    [8] => 14
)
bool(false)

参考：php实现二分查找法

二分查找时间复杂度计算方法

二分查找原理：有目标元素t和长度为n的有序数组a，查找t在a中的位置。首先取中间元素c = a[n/2]与t比较。
如果t和c相等则返回，如果t比c小，则从左侧部分继续取中间元素c，否则从右侧部分取中间元素进行比较，依次循环。
所以时间复杂度的计算就是循环次数的计算，如下推导：

次数 剩余操作元素数目
1 n
2 n/2
3 n/4
4 n/8
.. ….
k n/(2^(k-1))

最终剩余操作元素数目为n/(2^(k-1)) >=1，去除常数计算即：2^k = n,复杂度为O(log2n)以2为底n的对数

Twitter Snowflake

核心思想
snowflake是twitter开源的分布式ID生成算法，其核心思想是：
产生一个long型(64bit)的ID，使用其中41bit作为毫秒数，10bit作为机器编号，12bit作为毫秒内序列号。
这个算法单机每秒内理论上最多可以生成1000*(2^12)个，也就是大约400W的ID，完全能满足业务的需求。

实现

1
2
| 41 bits: Timestamp | 3 bits: 区域 | 10 bits: 机器编号 | 10 bits: 序列号 |
return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift) | (workerId << workerIdShift) | sequence;
  • 毫秒数计算：需要选择某一天的毫秒级时间戳为基准时间戳，然后用当前时间戳与基准时间戳相减
  • 序列号计算：同一毫秒内序列号自增，超过最大值则溢出等待下一毫秒
  • 最后分别对Timestamp、区域、机器编号、序列号分别向左做相对应的位运算，然后进行与操作得到最终的唯一id
    注意
  • 需要控制好所有服务器的时间，使用统一的ntp时间服务器，否则生成的id无法保持增长趋势
  • 这个id可用的时间大概是：2^41/1000/3600/24/365 ≈ 79年

检测数组中是否存在重复数字

问题描述

有长度为n的数组，内容是n，里面当然会有些重复的（只有重复2次的情况），举个例子 8,1,2,3,4,5,2,8 找出重复的数字

注意：特殊条件：长度为n，内容是n

思路一

循环一遍，把读取过的数据放入一个数据结构中，比如“哈希表”中，再每次判断哈希表中是否已经存在，来判断是否重复

思路二

使用当前数组的“索引”和“这个索引的数据是否为负数”来做共同承担“哈希表”的职责。
遍历数组的值，值-1作为索引值，也就是哈希值，重复的值对应生成的索引值是一样的，
这时候将该索引值对应的value变为负数，如果下次重复的值作为索引获取value小于1则认为是重复的。

1
2
3
4
5
6
7
8
9
10
11
def a( nums):
    b = []
    for x in nums:
        if nums[abs(x) - 1] < 0:
            b.append(abs(x))
        else:
            nums[abs(x) - 1] *= -1
    return b

if __name__ == '__main__':
    print(a([8,1,2,3,4,5,2,8]))

德州扑克算法

问题描述

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2-10为数字本身，A为1，J为11，Q为12，K为13， 而大小王可以看成任意数字，如何实现？

实现思路

由于大小王是特殊数字，暂且把他们看作为0，拿到5张牌后去掉大小王，然后进行排序，排序后只需要判断相邻两张牌不能重复，
如果重复则不是顺子，如果不是顺子则需要判断最大值与最小值的差与0的个数的关系。

  1. 确认5张牌中除了0，其余数字没有重复的（可以用表统计的方法）;
  2. 满足这样的逻辑：（max，min分别代表5张牌中的除0以外的最大值最小值）
    如果没有0，则max-min=4，则为顺子，否则不是
如果有一个0，则max-min=4或者3，则为顺子，否则不是
如果有两个0，则max-min=4或者3或者2，则为顺子，否则不是
    最大值和最小值在1）中就可以获得，这样就不用排序了。

扩展阅读