冒泡，选择，插入，希尔，快排，二分

def 冒泡(a):
    """
    冒泡循环，两两比较
    时间复杂度: O(n2)
    空间复杂度O(1)
    """
    for i in range(len(a) - 1):
        for j in range(len(a) - i - 1):
            if a[j] < a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    print("冒泡：%s" % a)


def 选择(a):
    """
    找出最大值下标与最后一位交换
    时间复杂度：O(n2)
    """
    for i in range(len(a) - 1):
        max_i = 0
        for j in range(len(a) - i):
            if a[max_i] < a[j]:
                max_i = j
        a[max_i], a[len(a) - 1 - i] = a[len(a) - 1 - i], a[max_i]
    print("选择：%s" % a)


def 插入(a):
    """
    从第二位开始循环往后，往前比较，如果2位小于1位，则交换，保证大数在后，从小到大
    时间复杂度：O(n2)
    空间复杂度O(1)
    """
    for i in range(1, len(a)):
        while i > 0:
            if a[i] < a[i - 1]:
                a[i], a[i - 1] = a[i - 1], a[i]
                i -= 1
            else:
                break
    print("插入：%s" % a)


def 希尔(a):
    """
    插入排序的中段分组模式，从中分开，每次中点g分二，分组进行插入排序
    时间复杂度: O(n1.5)
    空间复杂度O(1)
    """
    g = len(a) // 2
    while g >= 1:
        for i in range(g, len(a)):
            while i > 0:
                if a[i - g] > a[i]:
                    a[i], a[i - g] = a[i - g], a[i]
                    i -= 1
                else:
                    break
        g //= 2
    print("希尔：%s" % a)


def kuaipai(a):
    """
    时间复杂度: O(N*logN)
    O(nlogn)
    """
    if len(a) < 2:
        return a
    mid = a[len(a) // 2]
    left, right = [], []
    a.remove(mid)
    for i in a:
        if i >= mid:
            right.append(i)
        else:
            left.append(i)
    return kuaipai(left) + [mid] + kuaipai(right)
    

def 二分查找递归(s, l, lenn, num):
    if end >= start:
        mid = (start + end) // 2
        if arr[mid] == num:
            print("找到了，在 %d 位" % mid)
        elif arr[mid] > num:
            erfen(arr, start, mid - 1, num)
        else:
            erfen(arr, mid + 1, end, num)
    else:
        print("查无此数")


if __name__ == '__main__':
    a = [5, 1, 9, 0, 4, 3, 2, 7, 8, 6, 456]
    冒泡(a[::])
    print(a)
    选择(a[::])
    print(a)
    插入(a[::])
    print(a)
    希尔(a)
    print(a)
    二分查找递归(a, 0, len(a)-1, 0)