li = [1, 2, 3, 4, 5, 6, 7, 8, 9]

val = 5

def search(li, val):

    low = 0

    high = len(li) - 1

    while low <= high:

        mid = (low + high) // 2

        if val == li[mid]:

            return mid

        elif val < li[mid]:

            high = mid + 1

        else:

            low = mid - 1

    return 'no'

print(search(li, val))

li = [1, 12, 4, 7, 88, 22, 4, 8, 23]

for i in range(len(li) - 1):

    exchange = False

    for j in (range(len(li) - i - 1)):

        # 前一项与后一项比大小,大的交换排到后边去

        if li[j] > li[j + 1]:

            li[j], li[j + 1] = li[j + 1], li[j]

            exchange = True

    if not exchange:

        break

print(li)

li = [1, 12, 4, 7, 88, 22, 4, 8, 23]

for i in range(0, len(li) - 1):

    mini = i

    for j in range(i, len(li)):

        # 选择一个最小的记录

        if li[j] < li[mini]:

            mini = j

    # 将当前位置于最小的交换

    li[i], li[mini] = li[mini], li[i]

print(li)

li = [1, 12, 4, 7, 88, 22, 4, 8, 23]

for i in range(1, len(li)):

    tem = li[i]

    j = i - 1

    # 取一个数,插入到比他小的数的位置的后边,其他的数的下标向后移动

    while j > 0 and li[j] > tem:

        li[j + 1] = li[j]

        j -= 1

    li[j + 1] = tem

print(li)

import random

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(li, left, right):

    tem = li[left]

    while left < right:

        while li[right] >= tem and left < right:

            right -= 1

        li[left] = li[right]

        while li[left] <= tem and left < right:

            left += 1

        li[right] = li[left]

    li[left] = tem

    return left

# 减少递归深度[1000,999,....,0]

def random_partition(li, left, right):

    i = random.randint(left, right)

    li[i], li[left] = li[left], li[i]

    return partition(li, left, right)

if __name__ == '__main__':

    li = [random.randint(0, 10000) for i in range(1000)]

    print(li)

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

    print(li)

def quick_sort2(li):

    if len(li) < 2:

        return li

    tmp = li[0]

    left = [v for v in li[1:] if v <= tmp]

    right = [v for v in li[1:] if v > tmp]

    left = quick_sort2(left)

    right = quick_sort2(right)

    return left + [tmp] + right