def bubble_sort(a):
    # 冒泡排序
    for i in range(len(a)):
        # 主要是判断当前这一轮过去有没有交换，
        # 如果有交换就将其赋值为True,如果没交换说明这一轮过去顺序都是从小到大，直接跳出循环即可。
        sign = False
        for j in range(0, len(a)-1-i):
            if a[j] > a[j+1]:
                temp = a[j+1]
                a[j+1] = a[j]
                a[j] = temp
                sign = True
        if sign == False:
            break
    return a

def insert_sort(a):
    # 直接插入排序
    for i in range(len(a)):
        temp = a[i]
        j = i-1
        while a[j] > temp and j >= 0:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = temp
    return a

def select_sort(a):
    # 简单选择排序
    for i in range(len(a)):
        k = i
        min = a[i]
        for j in range(i+1, len(a)):
            if a[j] < min:
                min = a[j]
                k = j

        temp = a[k]
        a[k] = a[i]
        a[i] = temp
    return a


def quick_sort(a, low, high):
    # 快速排序算法
    i = low
    j = high
    if low > high:
        return
    if i < j:
        temp = a[i]
        while i != j:
            while j > i and a[j] > temp:
                j -= 1
            if j > i:
                a[i] = a[j]
                i += 1
            while j > i and a[i] < temp:
                i += 1
            if j > i:
                a[j] = a[i]
                j -= 1
        a[i] = temp
    quick_sort(a, low, i-1)
    quick_sort(a, i+1, high)
    return a


# 下面是归并排序的算法  分两步: 1.形成初始化归并段。 2.归并阶段
def fen_duan(list):
    # 分段
    if len(list) <= 1:
        return list
    zhong = int(len(list) / 2)
    left = fen_duan(list[:zhong])   # 一直递归下去进行分段直到剩下一个数
    right = fen_duan(list[zhong:])
    return merge(left, right)
def merge(left, right):
    # 合并段+排序
    i, j = 0, 0
    array = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            array.append(left[i])
            i += 1
        elif left[i] > right[j]:
            array.append(right[j])
            j += 1
    if i < len(left):
        array += left[i:]
    if j < len(right):
        array += right[j:]
    return array

# 下面是堆排序的算法(本次采用大顶堆)  # 一个是排序  一个是调整堆
def Sift(a, low, high):
    # 调整堆
    i = low
    j = 2*i   # 当前这个双亲的左孩子开始调整树
    temp = a[i]
    while j <= high:
        if j < high and a[j] < a[j+1]:   # 如果右孩子大,则将j指向右孩子
            j += 1
        if temp < a[j]:    # 此时双亲小于右孩子  则右孩子和双亲换位置
            a[i] = a[j]
            i = j          # 修改i和j的值, 以便继续向下调整
            j = 2*i
        else:
            break
    a[i] = temp
def heapSort(a):
    for i in range(len(a)//2-1, -1, -1):   # len(a)//2-1 是最后一个双亲节点的索引
        Sift(a, i, len(a)-1)
    for i in range(len(a)-1, -1, -1):
        temp = a[0]    # 将头取出来
        a[0] = a[i]    # 将树的最后一个节点放在头
        a[i] = temp    # 将头放到最后
        Sift(a, 0, i-1)
    return a



if __name__ == '__main__':
    a = [3, 4, 31, 61, 16, 5, 0, 21, 7]    # 随机给出一些数字

    # result_b = bubble_sort(a)
    # print("冒泡排序的结果:", result_b)

    # result_i = insert_sort(a)
    # print("直接插入排序的结果:", result_i)

    # result_s = select_sort(a)
    # print("简单选择排序的结果:", result_s)

    # result_q = quick_sort(a, 0, len(a)-1)
    # print("快速排序的结果:", result_q)

    # result_m = fen_duan(a)
    # print("归并排序的结果:", result_m)

    result_h = heapSort(a)
    print("堆排序的结果:", result_h)