list

排序

二分法查找

可迭代对象

迭代器

元组

排序

​ 冒泡排序 选择排序 插入排序 希尔排序 堆排序 快速排序 哈希排序 基数排序

冒泡排序

​ 思路：两两比较 将交换较大值或者较小值

a = [2,44,23,1,7,3]

def sort(arr):
    loop = len(arr) - 1
    # 控制趟数
    for i in range(0, loop):
        # 控制每一趟比较的次数
        for j in range(0, loop - i):
            if arr[j] > arr[j+1]:
                # 如果后一个 小于 前一个 交换两个元素的位置
                arr[j], arr[j+1] = arr[j+1], arr[j]

sort(a)
print(a)
# 时间复杂度O(n**2)
# 空间复杂度O(1)

选择排序

​ 思想：固定一个位置 然后 用该位置上的数 不断的和其之后的每一个元素比较

​ 第0趟 找到最小值 将其放到第0个位置

​ 第1趟 找到次小值 将其放到第1个位置

双层循环

外层循环 比较趟数

内存循环 比较次数和交换次数

a = [34, 52, 67, 39, 10, 7]

def sort(arr):
    loop = len(arr) - 1
    for out in range(0, loop):
        for i in range(out+1, len(arr)):
            if arr[out] > arr[i]:
                arr[out], arr[i] = arr[i], arr[out]
        # 时间复杂度O(n**2)
# 空间复杂度O(1)

# 选择排序实现2
a = [34, 52, 67, 39, 10, 7]
# 在每一趟循环 找到最小值的下标， 本趟循环结束 再将我们需要需要固定的位置所对应的元素 与
# 最小值所对应的元素交换
def sort(arr):
    for out in range(0, len(arr) - 1):
        min_index = out
        for i in range(out+1, len(arr)):
            if arr[i] < arr[min_index]:
                min_index = i
        # 得到最小值所对应的下标 然后将我们的固定的位置和最小值固定的位置交换
        arr[out], arr[min_index] = arr[min_index], arr[out]

插入排序

​ 列表 a

​ 给a[i]元素，在a[0:i-1]这个有序范围 找到合适的位置插入

​ 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

a = [34, 52, 67, 39, 10, 7]

def sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
sort(a)
print(a)
# 时间复杂度O(n**2)
# 空间复杂度O(1)

二分法查找(数组必须有序《重要》)

假设：数组 my_list

​ 待查找的元素

（1）确定该区间的中间位置K（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找

前提：数组是升序 my_list = [1,22,43,55,56] 待查找元素 56

a = [2,34,55,67,77]

def bin_search(array, obj):
    """
    二分法查找
    :param array: 待搜索数组
    :param obj: 待搜索元素
    :return: 下标
    """
    low = 0
    height = len(array)

    while low < height:
        mid = (low + height) // 2
        if array[mid] < obj:
            # 向右 height不变 low = mid + 1
            low = mid + 1
        elif array[mid] > obj:
            # 向左移动
            height = mid
        else:
            return mid

    else:
        # 没找到 返回-1
        return -1

res = bin_search(a, 94)
print(res)

列表生成式

​ 快速生成一个列表

​ 语法格式

        [循环变量 for 循环变量 in 序列 if 判断条件]

​ 例子：

    res1 = [i for i in range(0, 12, 2)] 没有判断条件
    res3 = [i for i in range(12) if i % 2==0] 有判断条件的

字典生成式

a = [(1,2), ("name","lucy"), ("age", 20)]

res = {key:value for key, value in a}
print(res)

可迭代对象

通俗的讲 就是for可以直接遍历的 字符串 list dict set tuple

判断：

​ isinstance（变量名， 类名）

​ 功能：帮助我们判断变量是不是 这个类名的实例

​ Iterable

from collections import Iterable，Iterator
a = 10
res = isinstance(a, Iterable)
print(res) ---->False

b = [1,2,4,4]
print(isinstance(b, Iterable)) --->True

迭代器

​ 列表生成式 能帮我们快速生成一个列表 但是是全都在内存 如果列表长度过大 而是用的数量还少 那将对内存造成严重的浪费

​ 注意：迭代器对象不能像list set tuple str等通过下标去访问

​ 迭代器是可以迭代的对象

​ 可迭代的对象不一定是迭代器 比如（字符串 列表 字典 元组等）

​ python给我们提供了迭代器来优化此问题：不浪费内存，当你使用的时候 他才给你计算拿出来

​ 声明：1 将列表生成时的中括号 变成小括号

​ 2 函数与yield关键字组合 形成一个迭代器

​ yield与return区别：return 结束函数

​ 而yield只是停止了迭代器（函数）的调用

​ 都可以返回值

​ 访问：使用内置next(迭代器对象)函数

​ 当我们的迭代器对象为空的时候 报错

可迭代对象转成迭代器

​ iter函数（可以迭代的对象）

元组

​ （1， ）

​ 注意：当我们直接使用括号表示一个元组的时候 如果只有一个元素 为了防止歧义 我们需要在元素后加一个逗号

操作：

​ 元组不可以修改

​ 但是可以使用+或者*

​ 可以通过下标访问

​ count（元素） ：统计元素在元组里出现的次数

​ index（元素）： 查找第一个匹配到的元素的下标

​ 如果元素不在元组 那么会报错

任务

1 排序算法

2 查找算法

​ 理论加代码

3 迭代器执行过程