高阶函数（High-order Function）

​ 数学概念 y = f(g(x))

​ 在数学和计算机科学中，高阶函数应当是至少满足下面一个条件的函数

​ 接受一个或多个函数作为参数

​ 输出一个函数

sorted函数原理

练习：自定义sort函数

仿照内建函数sorted，请自行实现一个sort函数（不用使用内建函数），能够为列表元素排序思考：通过练习，思考sorted函数的实现原理，map、filter函数的实现原理

思路：

​ 内建函数sorted函数，它返回一个新的列表，使用reverse可以设置升序或降序，使用key可以设置一个用于比较的函数（自定义函数也要实现这些功能）

​ 新建一个列表，遍历原列表，和新列表中的当前值依次比较，决定带插入数插入到新列表的什么位置

import random


def sort(iterable, *, key=None, reverse=False):
    newlist = [0] * len(iterable)
    iterable1 = iterable.copy()
    if key:
        for i in range(len(iterable)):
            iterable1[i] = key(iterable[i])
    for i in range(0, len(iterable1)):
        c = i
        newlist[i] = iterable1[i]
        if i > 0:
            for j in range(i):
                w = newlist[i - j - 1] < iterable1[i] if reverse else newlist[i - j - 1] > iterable1[i]
                if w:
                    newlist[i - j] = newlist[i - j - 1]
                    c = i - j - 1
                else:
                    break
            newlist[c] = iterable1[i]
    return newlist


a = [i for i in range(1, 10)]
# a = ['a', 'b', 'c', 'd', 1, 2, 3, 4]
random.shuffle(a)
print(a)
print(sort(a))
print(a)

内建高阶函数

排序sorted

定义sorted(iterable, *, key=None, reverse=False) ->list

过滤filter

​ 定义filter(function, iterable)

​ 对可迭代对象进行遍历，返回一个迭代器 是惰性的，需要催动

​ function参数是一个参数的函数，且返回值应当是bool类型，或其返回值等效布尔值。

​ function参数如果是None，可迭代对象的每一个元素自身等效布尔值

print(list(filter(lambda x: x % 3 == 0, [1, 9, 55, 150, -3, 78, 28, 123])))
#结果
[9, 150, -3, 78, 123]

print(list(filter(None, range(5))))
#结果
[1, 2, 3, 4]

print(list(filter(None, range(-5, 5))))
#结果
[-5, -4, -3, -2, -1, 1, 2, 3, 4]

映射map

​ 定义map(function, *iterables) -> map object

​ 对多个可迭代对象的元素，按照指定的函数进行映射

​ 返回一个迭代器

print(list(map(lambda x: 2 * x + 1, range(10))))
#结果
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print(dict(map(lambda x: (x % 5, x), range(500))))
#结果
{0: 495, 1: 496, 2: 497, 3: 498, 4: 499}

print(dict(map(lambda x, y: (x, y), 'abcde', range(10))))
#结果
{'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4}