P&G小站

# 编程思想-查找排序

# 算法入门

算法（Algorithm）：⼀个计算过程，解决问题的⽅法

Niklaus Wirth: “程序=数据结构+算法”

# 时间复杂度

时间复杂度：⽤来评估算法运⾏效率的⼀个式⼦

  • ⼀般来说，时间复杂度⾼的算法⽐复杂度低的算法慢
  • 常⻅的时间复杂度（按效率排序）
    • O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

快速判断算法复杂度（适⽤于绝⼤多数简单情况）

  1. 确定问题规模 n
  2. 循环减半过程 -> logn
  3. k层关于n的循环 -> n的k次方

# 空间复杂度

空间复杂度：⽤来评估算法内存占⽤⼤⼩的式⼦

  • 空间复杂度的表示⽅式与时间复杂度完全⼀样
    • 算法使⽤了⼏个变量：O(1)
    • 算法使⽤了⻓度为n的⼀维列表：O(n)
    • 算法使⽤了m⾏n列的⼆维列表：O(mn)
  • "空间换时间"

# 递归的两个特点

  • 调用自身
  • 结束条件

# 顺序查找

def linear_search(data, value):
    for index, item in enumerate(data):
        if item == value:
            return index
    
    return -1
  • 时间复杂度 O(n)
  • 列表内置函数 index 的算法

# 二分查找

def bin_search(data, value):
    low, high = 0, len(data) - 1
    
    # 调整下标 low 或 high 从而问题规模不断减小
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == value:
            return mid
        elif data[mid] > value:  # 中间值大于查找值，往小的区间缩进
            high = mid - 1
        else:
            low = mid + 1
    return -1
  • 有序列表(如升序)，定义合适的索引变量 low mid high
  • 时间复杂度 O(logn)

# 冒泡排序

  • 列表每两个相邻的数，如果前⾯⽐后⾯⼤，则交换这两个数
  • ⼀趟排序完成后，则⽆序区减少⼀个数，有序区增加⼀个数
  • 代码关键点：趟、⽆序区范围
  • 时间复杂度：O(n2)
def bubble_sort(li):
    for i in range(len(li)-1):
        # 一趟操作
        exchange = False    # ⼀趟排序没有发⽣交换，则说明列表有序
        for j in range(len(li) - i - 1):    # 无序区范围
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j+1], li[j]
                exchange = True

        if not exchange:
            return

# 选择排序

  • ⼀趟排序记录最⼩的数，放到第⼀个位置
  • 再⼀趟排序记录记录列表⽆序区最⼩的数，放到第⼆个位置，重复操作
  • 算法关键点：有序区和⽆序区、⽆序区最⼩数的位置
  • 时间复杂度：O(n2)
def select_sort(li):
    for i in range(len(li) - 1):
        # 取第一元素作为最小比对值
        min_index = i   # i 如何用，range 有开头和结尾两个参数，控制好无序区
        for j in range(i+1, len(li)):
            if li[j] < li[min_index]:
                min_index = j
        if min_index != i:
            li[i], li[min_index] = li[min_index], li[i]

# 插入排序

  • 初始时⼿⾥(有序区)只有⼀张牌
  • 每次(从⽆序区)摸⼀张牌，插⼊到⼿⾥已有牌的正确位置
  • 时间复杂度：O(n2)
def insert_sort(li):
    # 取第一张牌作为有序的初始值
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1  # 遍历有序区
        while j >= 0 and tmp < li[j]:
            li[j + 1] = li[j]   # 不断后移一个为 tmp 留位置
            j = j - 1
        li[j + 1] = tmp

# 快速排序

  • 取⼀个元素p（第⼀个元素），使元素p归位
  • 列表被p分成两部分，左边都⽐p⼩，右边都⽐p⼤
  • 递归完成排序
# 一次归位
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]

    data[left] = tmp
    return left


# 快速排序框架
def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)
  • 时间复杂度：O(nlogn)
  • 快速排序的问题
    • 最坏情况
    • 递归限制

# 堆排序

# 堆排序前传

  • 完全⼆叉树：叶节点只能出现在最下层和次下层，并且最下⾯⼀层的结点都集中在该层最左边的若⼲位置的⼆叉树
  • 二叉树树的顺序存储方式
    • 父节点 -> 左孩子: i -> 2 * i + 1
    • 父节点 -> 右孩子: i -> 2 * i + 2
    • 左右孩子 -> 父节点 (i - 1) // 2

# 什么是堆

堆：⼀种特殊的完全⼆叉树结构

  • ⼤根堆：⼀棵完全⼆叉树，满⾜任⼀节点都⽐其孩⼦节点⼤
  • ⼩根堆：⼀棵完全⼆叉树，满⾜任⼀节点都⽐其孩⼦节点⼩

堆的向下调整性质

  1. 假设根节点的左右⼦树都是堆，但根节点不满⾜堆的性质
  2. 可以通过⼀次向下的调整来将其变成⼀个堆

堆排序过程

  1. 建⽴堆(农村包围城市，从后往前)
  2. 得到堆顶元素，为最⼤元素
  3. 去掉堆顶，将堆最后⼀个元素放到堆顶，此时可通过⼀次调整重新使堆有序
  4. 堆顶元素为第⼆⼤元素
  5. 重复步骤3，直到堆变空
def sift(data, low, high):
    """
    一次向下调整
    前置条件：左右子树都是堆，但是父节点不是最大值
    目标结果：调整为堆
    :param data: 列表
    :param low: 堆的根节点位置
    :param high: 堆最后一个元素位置
    :return:
    """
    i = low
    j = 2 * i + 1
    tmp = data[i]

    while j <= high:
        if j + 1 <= high and data[j + 1] > data[j] : # 右孩子存在且较大
            j = j + 1

        # j 位置 和 tmp 位置相比较
        if data[j] > tmp:
            data[i] = data[j]   # i 一直是空位可以被代替，子字点上去到i位置
            i = j
            j = 2 * 1
        else:   # tmp 较大
            data[i] = tmp
            break

    data[i] = tmp   # j > high 跳出时，最后把tmp放回去

def heap_sort(data):
    n = len(data)
    # 建堆过程
    for i in range((n - 1 - 1) // 2, -1, -1):
        # i 建堆时调整的根，即low
        sift(data, i, n - 1)

    # 出数的过程
    for i in range(n - 1, -1, -1):
        # i 指向堆最后一个元素
        data[0], data[i] = data[i], data[0]
        sift(data, 0, i - 1)    # 堆顶即data[0], data[i - 1] 待一次调整
  • 时间复杂度：O(n2)

# 堆排序-topk问题

  • 现在有n个数，设计算法得到前k⼤的数 (k < n )

  • 解决思路：

    • 排序后切⽚ O(nlogn)
    • 排序LowB三⼈组 O(nk)
    • 堆排序 O(nlogk)

  • 堆排序思路

    • 取列表前k个元素建⽴⼀个⼩根堆, 堆顶就是⽬前第k⼤的数
    • 依次向后遍历原列表，对于列表中的元素，如果⼩于堆顶，则忽略该元素；如果⼤于堆顶，则将堆顶更换为该元素，并且对堆进⾏⼀次调整
    • 遍历列表所有元素后，倒序弹出堆顶
def sift(data, low, high):
    """
    一次调整为小根堆
    :param data: 列表
    :param low: 堆的根节点位置
    :param high: 堆最后一个元素位置
    :return:
    """
    i = low
    j = 2 * i + 1
    tmp = data[low]

    while j <= high:
        if j + 1 <= high and data[j + 1] < data[j]:  # 右孩子存在且较大
            j = j + 1

        # j 位置 和 tmp 位置相比较
        if data[j] < tmp:
            data[i] = data[j]   # i 一直是空位可以被代替，子字点上去到i位置
            i = j
            j = 2 * i + 1
        else:   # tmp 较大
            data[i] = tmp
            break
    else:
        data[i] = tmp   # j > high 跳出时，最后把tmp放回去


def top_k(data, k):
    heap = data[0:k]

    # 建堆过程 堆 heap 建堆
    for i in range((k - 1 - 1) // 2, -1, -1):
        # i 建堆时调整的根，即low
        sift(heap, i, k - 1)

    # 取剩余数一个一个与heap[0](我最小)相比较
    for i in range(k, len(data)):
        if data[i] > heap[0]:
            heap[0] = data[i]
            sift(heap, 0, k-1)

    # 出数的过程
    for i in range(k - 1, -1, -1):
        # i 指向堆最后一个元素
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)    # 堆顶即data[0], data[i - 1] 待一次调整

    return heap
上次更新: 8/30/2022, 12:38:23 PM

← 编程思想-数据结构 →