这些耳熟能详的算法你真的懂么

这些耳熟能详的算法你真的懂么

不知道你懂不懂,反正这李狗蛋我是当定了。对于很多比较经典的小算法,乍一听名字顿觉似曾相识兴奋不已,然而接下来大脑一片空白毫无头绪,只剩下那句永远的WTF回荡在脑海中。为了摆脱李狗蛋的囧境,笔者趁着闲来无事,研究了下几个出镜率较高的小算法,并基于pyhon完成其算法实现。

 1、归并排序 

归并排序算法是采用分治法的一个非常典型的应用,何谓分治,简单来讲就是化整为零,将大块拆成多个小块,分而治之。其算法原理是先把序列划分为n个子序列,然后对每个子序列排序,最后将子序列合并得到一个有序的最终序列。归并排序的算法我们通常用递归实现,先把待排序区间以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间。

def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    #对左右子区间通过递归调用,使左右子区间都有序
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    #merge函数用来将左右区间合并为最终排好序的结果序列
    def merge():
        r, l=0, 0
        result=[]
        while l<len(left) and r<len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        #通过上边的比较,最终left[l:]和right[r:]必有一个为空,剩下不为空的区间则包含了最后一部分数值较大的有序序列,直接追加到结果序列之后即可
        result += left[l:]
        result += right[r:]
        return result
    return merge()

通过例子可以看到,如果序列的长度为n=8,拆分为子序列要经过8/2,4/2,2/2这三步,而每个子序列都要经过merge_sort,也就是要经过log8=3次,每次归并要经过的最大比较次数为n,则总计要比较nlogn次,所以归并排序的时间复杂度为O(nlogn)。归并排序不是就地排序即不是在原序列上进行的,而是最终产出一个长度为n的新序列,所以其空间复杂度为O(n)。归并排序比较占用内存,但却是一种效率高且稳定的算法,效率仅次于快速排序,稍后列举完几个排序算法之后会给出实际的对比数据供参考。

 2、快速排序 

快速排序也是分治法的应用算法之一。其原理是:首先选中一个基准值,一般为中间值,然后序列中的其他值与基准值做比较,小于基准值的放入一个数组A中,大于基准值的放入另一个数组B中,只要数组A和数组B是有序的,那么A+基准值+B则为最终的排好序的结果。

def quick_sort(seq):
    if len(seq) < 2:
        return seq
    small_list = []
    big_list = []
    #median为基准值
    median_index = int(len(seq)/2)
    median = seq[median_index]
    front = seq[:median_index]
    end = seq[median_index+1:]
    for num in chain(front, end):
        if num > median:
            big_list.append(num)
        else:
            small_list.append(num)
    return quick_sort(small_list) + [median] + quick_sort(big_list)

从示例中可以看到,快速排序也是需要不断的二等分,所以也需要递归logn个子序列,跟归并算法有点相似,但是由于每次都会抽取一个基准值,所以每个子序列需要比较n-1次(n表示子序列长度,时间复杂度计算中不作过细区分,而且忽视常量),所以快速排序的时间复杂度也是O(nlogn),但是效率是高于归并排序的,因为n值较小。

 3、冒泡排序 

冒泡排序原理:从第一个元素开始,依次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。经过这样的一遍比较,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较,也就是排序完成了。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”。

def bubble_sort(l):
    l_len = len(l)
    while l_len > 1:
        index = range(l_len-1)
        for i in index:
            if l[i] > l[i+1]:
                l[i], l[i+1] = l[i+1], l[i]
        l_len -= 1

通过示例可以看到,要经过两层循环的比较,如果原序列是有序的话其时间复杂度为O(n),但这种情况比较少见,所以冒泡排序一般情况下的时间复杂度是O(n^2)。冒泡排序是就地排序,所以没有额外空间的消耗。但是冒泡排序每次遍历都需要做元素交换操作,这也就导致其排序效率比较低下。

 4、直接插入排序 

直接插入排序算法把要排序的数组分成两部分:第一部分包含了已排好序的数组A,而第二部分包含了无序的待插入元素的数组B。每次B中取一个元素,从右向左依次与数组A中的元素比较,直到找到合适位置,然后将该元素插入到A中,使A继续保持有序,如此往复,直到整个数组排序完成。

def insert_sort(l):
    #开始时假设l[0:1]就是已排好序的数组A,l[1:]为待排序的数组B
    #所以索引从1开始,遍历B,不断插入到数组A中
    for i in range(1, len(l)):
        #待插入的元素
        insert = l[i]   
        #如果已排好序数组A的最右边的元素大于待插入元素
        if l[i-1] > l[i]: 
            #index用来记录待插入元素的位置
            index = i 
            #从右向左依次与待插入元素做比较,直到找到合适的位置
            while index > 0 and l[index - 1] > insert:
                # 把已经排序好的元素后移一位,留下需要插入的位置
                l[index] = l[index - 1]     
                index -= 1
            l[index] = insert # 把需要排序的元素,插入到指定位置
    return l

示例中可以看到也是两层循环,但是有条件限制l[i-1] > l[i],如果序列本身是有序的则只需要遍历n次,时间复杂度则为O(n);如果是无序的,当然这是普遍的情况,所以其普遍的时间复杂度为O(n^2)

 5、简单选择排序 

简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,经过多次遍历,直到所有元素排完为止。简单选择排序是不稳定排序。所谓的不稳定排序并不是说排序结果正确性的不稳定,判断是否为稳定排序的依据是排序前相邻的两个相等的元素,在排序后是否依旧相邻并且位置索引没有变化,即是否会有多余的交换操作,因为这对效率是会造成影响的。

def simple_sort(l):
    l_len = len(l)
    for i in range(l_len):
        min_index = i
        for j in range(i+1, l_len):
            if l[min_index] >= l[j]:
                min_index = j
        #最小值的位置有变化时才做交换操作
        if min_index != i:
            l[i], l[min_index] = l[min_index], l[i]
    return l

由示例可见,简单排序也是双层循环,普遍情况下需要比较n^2次,所以其时间复杂度为O(n^2),但是交换操作次数最多为n次,这一点是要强于冒泡排序的。

关于排序的算法就列举这几个,接下来看下这几个排序算法的执行效率,先实现一个用于计时的装饰器用来统计运行时间

from random import shuffle 
from time import time
from functools import wraps

def timer(func):
    @wraps(func)
    def wrapper(*args, **kwds):
        start = time()
        result = func(*args, **kwds)
        elapsed = int((time() - start)*1000)
        print("{} elapsed: {}ms".format(func.__name__, elapsed))
        return result
    return wrapper

l = list(range(10000))
sort_funcs = [func for name, func in globals().items() if name.endswith("_sort")]
for func in sort_funcs:
    shuffle(l)
    #这里提醒一下,不要将timer装饰器通过语法糖@绑定到函数上,因为递归的关系,你懂得
    timer(func)(l)

输出如下:
simple_sort elapsed: 2429ms
merge_sort elapsed: 47ms
quick_sort elapsed: 15ms
bubble_sort elapsed: 6530ms
insert_sort elapsed: 3747ms
 6、二分查找 

二分查找也是采用分治策略的算法,采用二分查找的必要前提是保证序列是有序的,这点是非常重要的。其原理是将原序列从中间分为两个子序列A和B,并将中间值作为关键字与被查找的目标关键字做比较,如果相等则查找成功;如果目标值小于中间值,则从子序列A中查找;如果大于则从子序列B中查找。子序列的查找则重复上述过程直到目标命中。

def b_search(target, seq):
    '''二分查找'''
    low = 0
    high = len(seq) - 1
    while low <= high:
        mid = int((low+high)/2)
        guess = seq[mid]
        if target == guess:
            return mid
        if target < guess:
            high = mid -1
        else:
            low = mid + 1

def n_search(target, seq):
    '''简单查找'''
    for element in seq:
        if target == element:
            return seq.index(element)

二分查找每次都会将序列折中,然后在缩小范围后的子序列中查找,比如序列长度为n=8,目标值位于序列末尾,那么最多需要8/2, 4/2, 2/2三步就可以命中目标,可以看出有这样的关系2^3=8,需要的步数是以2为底数的log8=3,所以二分查找的时间复杂度为O(logn),其查找效率是非常高的,在长度为1024的序列中查找最多只需要10步,随着序列长度的增长,其相应的查找步数增速是很缓的。

示例中还列出了一种简单查找算法,简称傻找算法,就是从序列开头遍历比较,其时间复杂度是线性的O(n)。简单查找唯一的优势就是不需要序列是有序的,省去了排序的时间消耗。下面通过实际运行看下二者的效率差异

#序列长度1000w
n = 10000000
target = 9999999
l = list(range(n))
timer(b_search)(target, l)
timer(n_search)(target, l)

输出:
b_search elapsed: 0ms
n_search elapsed: 288ms

#序列长度1亿
n = 100000000
target = 99999999
l = list(range(n))
timer(b_search)(target, l)
timer(n_search)(target, l)

输出:
b_search elapsed: 0ms
n_search elapsed: 2732ms

可以看到二分超找在查找效率上是有绝对优势的,当然例子中的序列是有序,如果数据量巨大排序也是比较耗时的。所以使用哪种算法还得看实际场景,毕竟脱离实际需求的技术都是耍流氓!

 7、斐波那契数列 

斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、34、…… 这个数列从第3项开始,每一项都等于前两项之和。原理很简单,但是斐波那契数列是有重大意义的,因为其在数学和生活以及自然界中都非常有用,可参考知乎上为何斐波那契数列如此重要,那家伙总结的老到位了,学渣渗入- -!关于斐波那契数列的实现方法,笔者提供了两种:

def fib1(n, f=1, s=1, cache={}):
    '''递归版'''
    import sys
    sys.setrecursionlimit(99999)
    result = cache.get(n)
    if result is None:
        if n == 1:
            result = f
        if n == 2:
            result = s
        elif n > 2:
            result = fib1(n-2) + fib1(n-1)
        cache[n] = result
    return result

def fib2(n, result=[1, 1]):
    '''循环版'''
    if n == 1:
        return result[0]
    if n == 2:
        return result[1]
    for i in range(2, n):
        result.append(result[i-2] + result[i-1])
    return result[n-1]

递归版的实现增加了缓存机制,避免大量重复的计算;python3默认的最大递归深度也就是操作栈数为1000,由于递归版的基线条件为n==1或n==2,在n值较大时递归的层级太大了还没有到达基线条件的话就会导致堆栈溢出,所以递归版的先修改了操作栈数的最大值。通过下边的实际输出,可以看到两种版本的运行效率相差无几。

timer(fib2)(5000)
timer(fib1)(5000)

输出:
fib2 elapsed: 1ms
fib1 elapsed: 7ms
 这里再补充一个利用标准库functools中的lru_cache实现的带缓存的递归版本
from functools import lru_cache

@lru_cache(maxsize=1024)
def fib3(n, f=1, s=1):
    if n == 1:
        return f
    if n == 2:
        return s
    if n > 2:
        return fib3(n-2) + fib3(n-1)
Comments are closed.