datetime:2023-07-04 19:30

author:nzb

堆、桶排序及排序总结

堆

• 1、堆结构就是用数组实现的完全二叉树结构
• 2、完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
  • 大根堆：每一颗子树的最大值就是头结点的值
• 3、完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
  • 小根堆：每一颗子树的最小值就是头结点的值
• 4、堆结构的heapInsert与heapify操作
• 5、堆结构的增大和减少
• 6、优先级队列结构，就是堆结构

"""
idx = [0,1,2,3,4,5,6]
arr = [3,5,2,7,1,9,6]

         0
      /     \
    1        2
  /   \    /   \
 3     4  5     6

 size = 7
 i位置
 左孩子：2 * i + 1
 右孩子：2 * i + 2
 父：(i - 1) // 2

"""

• heapinsert：调整时间复杂度，往上走高度，O(logN)

def heap_insert(arr: list, index: int):
    """某个数现在在index位置，继续往上移"""
    parent_idx = max((index - 1) >> 1, 0)  # ">> 1" == "// 2"

    while arr[index] > arr[parent_idx]:  # 到头结点，arr[0] > arr[0] 肯定不满足
        arr[index], arr[parent_idx] = arr[parent_idx], arr[index]
        index = parent_idx
        parent_idx = max((index - 1) >> 1, 0)

• heapify：调整时间复杂度，往下走高度，O(logN)

def heapify(arr: list, index: int, heap_size: int):
    """某个数在index位置，能否往下移动"""
    left = 2 * index + 1  # 左孩子下标
    while left < heap_size:  # 下方还有孩子
        # 左右孩子哪个大
        largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
        # 父与孩子之间，哪个大，如果较大的子节点的值不大于当前节点的值，则堆调整完成
        if arr[largest] <= arr[index]:
            break
        arr[largest], arr[index] = arr[index], arr[largest]
        index, left = largest, 2 * largest + 1

堆排序

堆排序远远没有堆结构重要、堆排序远远没有堆结构重要、堆排序远远没有堆结构重要

• 1、先让整个数组都变成大根堆结构，建立堆的过程:
  • 1、从上到下的方法，时间复杂度为O(N*logN)
  • 2、从下到上的方法，时间复杂度为O(N)
• 2、把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
• 3、堆的大小减小成0之后，排序完成

# 大根堆调整
def heap_insert(arr: list, index: int):
    """某个数现在在index位置，继续往上移"""
    parent_idx = max((index - 1) >> 1, 0)  # ">> 1" == "// 2"

    while arr[index] > arr[parent_idx]:  # 到头结点，arr[0] > arr[0] 肯定不满足
        arr[index], arr[parent_idx] = arr[parent_idx], arr[index]
        index, parent_idx = parent_idx, max((index - 1) >> 1, 0)


# 大根堆调整
def heapify(arr: list, index: int, heap_size: int):
    """某个数在index位置，能否往下移动"""
    left = 2 * index + 1  # 左孩子下标
    while left < heap_size:  # 下方还有孩子
        # 左右孩子哪个大
        largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
        # 父与孩子之间，哪个大，如果较大的子节点的值不大于当前节点的值，则堆调整完成
        if arr[largest] <= arr[index]:
            break
        arr[largest], arr[index] = arr[index], arr[largest]
        index, left = largest, 2 * largest + 1


def heap_sort(arr: list):
    if not arr or len(arr) < 2:
        return

    # 首先变成大根堆 O(N*logN)
    for k in range(len(arr)):  # 时间复杂度：0(N)
        heap_insert(arr, k)  # 时间复杂度 O(logN)

    """
    变成大根堆优化版，不heap_insert，而是heapify
    假设，数不是一个一个加，而是给一个不是大根堆的数组，从下往上，一颗一颗小树搞成大根堆
    复杂度分析
        假设满二叉树，N个节点
        最后一层叶节点=N/2，每个节点往下复杂度，看一次1
        倒数第二层叶节点=N/4，每个节点往下复杂度，看一次1，往下移动一次1，代价2
        倒数第三层叶节点=N/8，每个节点往下复杂度，看一次1，往下移动两次2，代价3
        倒数第四层叶节点=N/16，每个节点往下复杂度，看一次1，往下移动两次3，代价4
        复杂度：①T(N) = N/2 + N/4 * 2 + N/8 * 3 + N/16 * 4 + N/32 * 5 + ...
        求：等号左右两边乘以2
        ②2T(N) = N + N/2 * 2 + N/4 * 3 + N/8 * 4 + N/16 * 5 + ...
        错位相减②-①：T(N) = N + N/2  + N/4 + N/8 + N/16 + ...
        等比数列求和公式：Sn = a(1-q^n)/(1-q), a=N, q = 2，忽略常数项
    所以时间复杂度：O(N)  
    """
    # # 大根堆优化版
    # for i in range(len(arr))[::-1]:
    #     heapify(arr, i, heap_size=len(arr))

    # 每个头结点（大根堆头结点最大）跟尾部交换，然后长度减一，O(N*logN)
    heap_size = len(arr)
    while heap_size > 0:  # 时间复杂度 0(N)
        heap_size -= 1
        arr[0], arr[heap_size] = arr[heap_size], arr[0]  # 空间复杂度： O(1)
        # 重新生成大根堆
        heapify(arr, 0, heap_size)  # 时间复杂度： O(logN)


data = [4, 6, 5, 2, 3, 1, 8, 7, 9, 10, 15, 13]
heap_sort(data)
print(data)

# 小根堆调整
def heap_insert(arr: list, index: int):
    parent_idx = max(0, (index - 1) >> 1)
    while arr[index] < arr[parent_idx]:
        arr[index], arr[parent_idx] = arr[parent_idx], arr[index]
        index, parent_idx = parent_idx, max(0, (index - 1) >> 1)


def heapify(arr: list, index: int, heap_size: int):
    left_idx = 2 * index + 1
    while left_idx < heap_size:
        smallest_idx = left_idx + 1 if left_idx + 1 < heap_size and arr[left_idx + 1] < arr[left_idx] else left_idx
        # 最小的都比父大，完成调整
        if arr[smallest_idx] >= arr[index]:
            break
        arr[index], arr[smallest_idx] = arr[smallest_idx], arr[index]
        index, left_idx = smallest_idx, 2 * index + 1

堆排序扩展题目

• 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

• 解决思路：利用小根堆，把数组前k+1，个数建立成小根堆，然后加一个，弹出最小的，因为每个元素移动的距离不超过k

import heapq


def heapq_sort_distance_less_k(arr: list, k: int):
    # pq = []
    # # 建立小根堆，heapq 默认就是小根堆
    # min_val = min(len(arr), k + 1)  # 怕给的 K 过大
    # # 为什么建立大小为 k 的小根堆，因为每个元素移动的距离不超过k，所以第k+1，肯定不会是最小值，如果是最小值，移到到根部就超过了k
    # for i in range(min_val):  # 移动不超过 k
    #     heapq.heappush(pq, arr[i])

    min_val = min(len(arr), k + 1)  # 怕给的 K 过大
    pq = arr[:min_val]
    heapq.heapify(pq)

    x = 0
    for y in range(min_val, len(arr)):
        heapq.heappush(pq, arr[y])  # 添加一个
        arr[x] = heapq.heappop(pq)  # 弹出一个
        x += 1
    # 没数了，把最后的堆，pop完
    while pq:
        arr[x] = heapq.heappop(pq)
        x += 1


data = [4, 6, 5, 2, 3, 1, 8, 7, 9, 10, 15, 13]
heapq_sort_distance_less_k(data, 5)
print(data)

• 一个数据流中，随时可以取得中位数

• 解决思路：大跟堆和小根堆配合

  • 第一个数入大根堆
  • 后续数字是否小于等于(<=)跟大根堆堆顶
    • 是：入大根丢
    • 否：入小根堆
  • 看大根堆和小根堆的大小，如果大小差值到达2，如果是，大小较大的堆弹出，进入大小较小的堆

import heapq


def middle_num(data: list):
    if not data:
        return

    hq_min = []
    hq_max = []
    for num in data:
        if not hq_max or num <= -hq_max[0]:
            heapq.heappush(hq_max, -num)  # 取反，就是大根堆，入栈和弹出的记得取反
        else:
            heapq.heappush(hq_min, num)

            # 保持平衡
        hq_max_len = len(hq_max)
        hq_min_len = len(hq_min)
        if abs(hq_max_len - hq_min_len) == 2:
            if hq_max_len > hq_min_len:
                heapq.heappush(hq_min, -heapq.heappop(hq_max))  # 取出来后记得取反
            else:
                heapq.heappush(hq_max, -heapq.heappop(hq_min))
    if (len(hq_max) + len(hq_min)) % 2 == 0:
        return (-hq_max[0] + hq_min[0]) / 2
    else:
        return -hq_max[0] if len(hq_max) > len(hq_min) else hq_min[0]


print(middle_num([]))
print(middle_num([1]))
print(middle_num([1, 2, 3, 4, 5, 6, 7]))
print(middle_num([1, 2, 3, 4, 5, 6, 7, 8]))
# None
# 1
# 4
# 4.5

注意

使用系统给的堆功能，相当于黑盒
你只能给它一个数，它给你弹出一个数，内部它会维护堆结构
你不能够，它已经维持好的堆结构，你想给它内部的某个位置变值，它的调整代价很高，只能每个值去扫一下看看需要heap_insert还是heapify，手写堆支持，如果你自己有这种需求，需要你自己手写

比较器的使用

• 1）比较器的实质就是重载比较运算符
• 2）比较器可以很好的应用在特殊标准的排序上
• 3）比较器可以很好的应用在根据特殊标准排序的结构上

# -*-: encoding: utf8 -*-
from filecmp import cmp


class Demo():

    def __init__(self, age):
        self.age = age

    def __gt__(self, other):
        """>"""
        return self.age > other.age

    def __ge__(self, other):
        """>="""
        return self.age >= other.age

    def __lt__(self, other):
        """<"""
        return self.age < other.age

    def __le__(self, other):
        """<="""
        return self.age <= other.age

    def __eq__(self, other):
        """=="""
        return self.age == other.age

    def __ne__(self, other):
        """!="""
        return self.age != other.age


if __name__ == '__main__':
    ins1 = Demo(5)
    ins2 = Demo(6)
    print(ins1 > ins2)
    print(ins1 >= ins2)
    print(ins1 < ins2)
    print(ins1 <= ins2)
    print(ins1 == ins2)
    print(ins1 != ins2)

桶排序

之前讲的所有排序都是基于比较的排序

不基于比较的排序一定要根据数据状况来定制的

桶排序思想下的排序

• 1）计数排序：每个词频统计下，计数一下
  • 一个数组，里面都是员工的整数年龄，员工年龄16~200，16岁以下
• 2）基数排序

排序总结

• 同样的值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的，否则没有
• 不具备稳定性的排序：
  • 选择排序：[3,3,3,1,3,3,3]，第一个位置的3跟1交换就破坏了稳定性
  • 快速排序：partition的时候会交换位置就做不到了
  • 堆排序：[5,4,4]，插入一个6，会跟第二个4做交换，就不具备稳定性
• 具备稳定性的排序：
  • 冒泡排序：[6,5,4,5,3,4,6]，如何做到，当2个数相等的时候，不做交换，比如两两比较到最后[5,4,5,3,4,6,6], 6和6不交换就做到了稳定性
  • 插入排序：[3,2,2]，往前看的时候，如果相等的时候，也不做交换，就可以做到稳定性
  • 归并排序：左边和右边相等的时候，先拷贝左边的，但是小和问题，当相等的时候是先拷贝右边的，这就丧失了稳定性
  • 一切桶排序思想下的排序
• 目前没有找到时间复杂度为O(NlogN)，额外空间复杂度为O(1)，又稳定的排序

• 一般选择随机快排，虽然归并、快排和堆排都是O(NlogN)，但是经过实验的检验，它的常数项是最低的
• 如果有空间的限制，用堆排
• 需要稳定性，用归并

常见的坑

• 1、归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴趣可以搜归并排序内部缓存法，那为什么不用堆排序？
• 2、“原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O(N^2)，那为什么不用插入？
• 3、快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”，空间复杂度变为O(N)，那为什么不用归并？
• 4、所有的改进都不重要，因为目前没有找到时间复杂度为O(NlogN)，额外空间复杂度为O(1)，又稳定的排序
• 5、有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，时间复杂度O(N)，空间复杂度O(1)，碰到这个问题，可以怼面试官。

工程上对排序的改进

• 充分利用O(N*logN)和O(N^2)排序各自的优势
• 稳定性的考虑
• 改进版本排序，比如一个大样本的排序，大样本的时候用随机快排，partition到小样本的时候用插入排序，而不再继续partition