今天参加了笔试，emmmmmmm，继续苦下功夫。

好习惯的养成：清晰的思路可以让代码快速成型。合适的注释让代码更加具备可读性。准备合适的工具做一个解释图或者动图。

1、桶排序

“”“
思路：这是一个整形数组，找到其最大值，设置（max+1）个空桶，将原数组开始投放到对应的桶（索引=num）里，再从桶里取出。
”“”

def bucket_sort_func(arr):
    if len(arr) < 2:
        return arr
    max_arr = max(arr)
    # 放空桶
    bucket = [0 for _ in range(max_arr+1)]
    for num in arr:
        bucket[num] += 1
    sort_arr = []
    for i in range(len(bucket)):
        if bucket[i] != 0:
            for ele in range(bucket[i]):
                sort_arr.append(i)
    return sort_arr

# 放回原数组
def bucket_sort(arr):
    res = bucket_sort_func(arr)
    for i in range(len(arr)):
        arr[i] = res[i]

2、堆排序

“”“
思路：首先了解什么是大根堆，一个构造大根堆的过程，一个将修复大根堆的过程。
‘”“

def heap_sort(arr):
    if len(arr) < 2:
        return arr
    for i in range(len(arr)):
        heap_insert(arr, i)
    size = len(arr)
    size -= 1
    arr[0], arr[size] = arr[size], arr[0]

    while size > 0:
        heapify(arr, 0, size)
        size -= 1
        arr[0], arr[size] = arr[size], arr[0]


def heap_insert(arr, index):
    # 构造大根堆
    # 出现一个BUG，最后一个数没有排好，问题见以下描述。必须要int，整除不可以！
    # index = 0
    # a = int((index - 1) / 2)
    # b = (index - 1) // 2
    # print(a, b)   打印结果 a=0,b=-1
    # while arr[index] > arr[((index-1)//2)]:
    #     arr[index], arr[((index-1)//2)] = arr[((index-1)//2)], arr[index]
    #     index = ((index-1)//2)
    while arr[index] > arr[int((index-1)/2)]:
        arr[index], arr[int((index-1)/2)] = arr[int((index-1)/2)], arr[index]
        index = int((index-1)/2)


def heapify(arr, index, size):
    # 调节大根堆
    left = index*2 + 1
    while left < size:
        if (left+1) < size and arr[left+1] > arr[left]:
            largest = left + 1
        else:
            largest = left
        if arr[largest] > arr[index]:
            largest = largest
        else:
            largest = index
        if largest == index:
            break
        arr[largest], arr[index] = arr[index], arr[largest]
        index = largest
        left = index*2 + 1

3、桶排序拓展

题目一：给定一个整型数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。
”“”
思路：根据max和min放空桶，这个桶里面应该包含判断是否为空的布尔值，放进来的最小值，放进来的最大值。开始投放数组，更新桶里面的参数。
“”“

# 待后续补充

题目二：求给定数组的中位数。
”“”
思路：一个大根堆，一个小根堆，保持平衡！
“”“

# 待后续补充

算法第三天温故知新之堆排序和桶排序

原文：https://www.cnblogs.com/burry/p/12664076.html