def insertion_sort(arr):
    """直接插入排序"""
    for i in range(1, len(arr)):
        for j in range(0, i):
            if arr[i] < arr[j]:
                arr.insert(j, arr.pop(i))
        print("第{}轮排序后结果为：{}".format(i, arr))
    return arr

def quick_partition(arr, low, high):
    i = (low - 1)  # 最小元素索引
    pivot = arr[high]
    for j in range(low, high):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort(arr, low, high):
    """快速排序"""
    if low < high:
        temp = quick_partition(arr, low, high)
        quick_sort(arr, low, temp - 1)
        quick_sort(arr, temp + 1, high)

def select_sort(arr):
    """选择排序"""
    sort_list = []
    min_index = 0
    while len(arr) != 0:
        # 取出余下数列中最小的值的索引
        for i in range(0, len(arr)):
            if arr[i] < arr[min_index]:
                min_index = i
        # 将值取出放入新数组
        sort_list.append(arr.pop(min_index))
        # 归零索引
        min_index = 0
    return sort_list

def bubble_sort(arr):
    """冒泡排序"""
    for t in range(len(arr) - 1):
        for i in range(len(arr) - 1 - t):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr

def merge_sort(arr):
    """归并排序"""
    # 计算中值
    mid = len(arr) // 2
    # 切割左右数组
    left = arr[:mid]
    right = arr[mid:]
    merge = []
    # 左边数组元素个数大于1时归并排序
    if len(left) > 1:
        left = merge_sort(left)
    # 右边数组元素个数大于1时归并排序
    if len(right) > 1:
        right = merge_sort(right)
    # 归并左右数组
    while left and right:
        if right[0] <= left[0]:
            merge.append(right.pop(0))
        else:
            merge.append(left.pop(0))
    merge.extend(left)
    merge.extend(right)
    return merge

def heap_sort(arr):
    """堆排序"""
    result = []
    while arr:
        # 初始化堆
        arr = min_heap(arr)
        # 取出堆顶元素
        result.append(arr.pop(0))
    return result

def min_heap(arr):
    """建最小堆"""
    arr = list(arr)
    le = len(arr)
    mid = le // 2
    for i in range(0, mid):
        temp = mid - i
        # 判断是否有右支
        if 2 * temp == le:
            # 无右支，比较左支并交换
            if arr[temp - 1] > arr[temp * 2 - 1]:
                arr[temp - 1], arr[temp * 2 - 1] = arr[temp * 2 - 1], arr[temp - 1]
        else:
            # 比较左右支,并与父节点交换
            if arr[temp * 2 - 1] > arr[temp * 2]:
                min_index = temp * 2
            else:
                min_index = temp * 2 - 1
            if arr[temp - 1] > arr[min_index]:
                arr[temp - 1], arr[min_index] = arr[min_index], arr[temp - 1]
    return arr

def shell_sort(arr):
    """希尔排序"""
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2
    return arr