# 冒泡排序,T(n) = O(n**2)
def bubble_sort(li):
    print(li)
    for i in range(len(li)-1):  # i代表第几趟
        for j in range(len(li) - i - 1): # j代表每趟过程中的下标
            if li[j] > li[j + 1]:
                li[j], li[j +1] = li[j + 1], li[j]
        print(li)
    return li


# bubble_sort([9,8,7,6,5,4,3,2,1])

2.选择排序,T(n) = O(n**2)

# 选择排序
def select_sort(li):
    for i in range(len(li)-1):
        min_index = i
        for j in range(i, len(li)):
            if li[j] < li[min_index]:
                min_index = j
        li[i],li[min_index] = li[min_index], li[i]
    return li
# print(select_sort([1,9,2,8,3,6,4,5,7]))

3.插入排序,T(n) = O(n**2)

# 插入排序,
def insert_sort(li):
    for i in range(1, len(li)):  # i代表每次摸到的牌的下标
        tmp = li[i]
        j = i - 1   # j代表手里最后一张牌的下标
        while True:
            if j < 0 or tmp >= li[j]:
                break
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tmp

    return li

4.快速排序,T(n) = O(nlogn)

# 快速排序
def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left,  mid-1)
        quick_sort(li, mid+1, right)


def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right] # 第一次不满足条件时，right值固定
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left]=tmp
    return left

print(quick_sort(li, 0, len(li)-1))
print(li)

5.堆排序,T(n) = O(nlogn)

# 堆排序
def sift(data, low, high):
    """
    调整函数
    data: 列表
    low：待调整的子树的根位置
    high：待调整的子树的最后一个节点的位置
    """
    i = low
    j = 2 * i + 1
    tmp = data[i]
    # i指向空位置
    while j<=high:      #领导已经撸到底了
        if j != high and data[j] < data[j+1]:
            j += 1
        #j指向数值大的孩子
        if tmp < data[j]:   #如果小领导比撸下来的大领导能力值大
            data[i] = data[j]
            i = j
            j = 2*i+1
        else:
            break       #撸下来的领导比候选的领导能力值大
    data[i] = tmp


def heap_sort(data):
    n = len(data)
    # 建堆
    for i in range(n//2-1, -1, -1):
        sift(data, i,  n - 1)
    # 挨个出数
    for high in range(n - 1, -1, -1):
        data[0], data[high] = data[high], data[0]
        sift(data, 0, high - 1)

6.归并排序，T(n) = O(nlogn)

# 归并排序
def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] <= li[j]:
            ltmp.append(li[i])
            i += 1
        else: # li[i]>li[j]
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1]=ltmp


def mergesort(li, low, high):
    if low < high:
        mid = (low + high) // 2
        mergesort(li, low, mid)
        mergesort(li, mid+1, high)
        merge(li, low, mid, high)

7.希尔排序

TODO...

8.基数排序

TODO