# 冒泡排序确定最小值
def bubble_sort_by_min(list):
    for i in range(0, len(list) - 1):
        flag = False
        # i为0, range函数取不到右端点
        for j in range(len(list) - 2, i - 1, -1):
            if list[j] > list[j + 1]:
                list[j], list[j+1] = list[j+1], list[j]
                flag = True
                print(list)
        if not flag:
            break


# 冒泡排序确定最大值
def bubble_sort_by_max(list):
    for i in range(len(list) - 1, 0, -1):
        flag = False
        for j in range(0, i):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]
                flag = True
        if not flag:
            break


# 选择排序
def selection_sort(list):
    for i in range(0, len(list) - 1):
        for j in range(i, len(list)):
            if list[i] > list[j]:
                list[i], list[j] = list[j], list[i]


# 插入排序
def insertion_sort(list):
    for i in range(1, len(list)):
        insert_num = list[i]
        # 从后向前比较
        j = i - 1
        while j != -1:
            if insert_num < list[j]:
                list[j+1] = list[j]
            else:
                break
            j -= 1
        list[j+1] = insert_num


# 归并排序
def merge_sort(list, l, r):
    # 确定出口
    if l >= r:
        return 0
    # 算中间位置
    res = 0
    mid = int((l + r) / 2)
    res += merge_sort(list, l, mid)
    res += merge_sort(list, mid + 1, r)

    # 合并两边
    temp = []
    i = l
    j = mid + 1
    while i <= mid and j <= r:
        if list[i] < list[j]:
            temp.append(list[i])
            i += 1
        else:
            res += mid - i + 1
            temp.append(list[j])
            j += 1

    # 将剩余的数填入数组
    while i <= mid:
        temp.append(list[i])
        i += 1
    while j <= r:
        temp.append(list[i])
        j += 1

    # 将temp赋值给原数组
    for i in range(0, len(temp)):
        list[i + l] = temp[i]
    return res


# 快速排序
def quick_sort(list, l, r):
    if l >= r:
        return
    # 初始化
    i = l - 1
    j = r + 1
    # 取中间值
    x = list[int((l + r) /2)]
    while i < j:
        while True:
            j -= 1
            if list[j] <= x:
                break
        while True:
            i += 1
            if list[i] >= x:
                break
        if i < j:
            list[j], list[i] = list[i], list[j]
        else:
            quick_sort(list, l, j)
            quick_sort(list, j + 1, r)


# 父节点向下移动
def push_down(heap, size, u):
    # 初始化
    t = u
    left = u * 2
    right = left + 1
    # 判断左孩子是否大于父节点
    if left <= size and heap[left] > heap[t]:
        t = left
    # 判断右孩子是否大于父节点
    if right <= size and heap[right] > heap[t]:
        t = right
    # 交换位置，进行递归
    if t != u:
        heap[t], heap[u] = heap[u], heap[t]
        # t为被换下的父节点
        push_down(heap, size, t)


# 子节点向上移动
def push_up(heap, u):
    while u // 2 and heap[u // 2] < heap[u]:
        heap[u // 2], heap[u] = heap[u], heap[u // 2]
        u //= 2


# 插入元素
def insert(heap, x):
    heap.append(x)
    push_up(heap, len(heap) - 1)


# 移除堆顶元素
def remove_top(heap, size):
    heap[1] = heap[size]
    size -= 1
    push_down(heap, size, 1)


# 堆排序
def heap_sort(heap, size):
    for i in range(1, size):
        push_up(list, i)

    # 拿出最大元素，放在最后
    for i in range(1, size):
        heap[1], heap[size] = heap[size], heap[1]
        size -= 1
        push_down(heap, size, 1)


# 计数排序

# 桶排序

# 基数排序

def get_pos(x, i):
    while True:
        i -= 1
        if i != 0:
            x //= 10
        else:
            break
    return x % 10


def radix_sort(list, n):
    cnt = []
    # 遍历位数
    for i in range(1, 4):
        # 清空
        cnt.clear()
        # 创建桶
        for j in range(0, 10):
            cnt.append([])

        # 按照每一位的大小来分配归属桶
        for j in range(0, n+1):
            cnt[get_pos(list[j], i)].append(list[j])

        k = 0
        for j in range(0, 10):
            for x in cnt[j]:
                list[k] = x
                k += 1


list = [0,5,4,3,2,1,3]

# bubble_sort_by_max(list)
# bubble_sort_by_min(list)
# selection_sort(list)
# insertion_sort(list)
# print(merge_sort(list, 0, len(list) - 1))
# quick_sort(list, 0, len(list) - 1)
heap_sort(list, len(list)-1)
# radix_sort(list, len(list) - 1)
print(list)