def linear_search(li,val):

    for ind ,v  in enumerate(li):

        if v==val:

            return ind

        else:

            return None

def binary_search(li,val):

    left = 0

    right = len(li)-1

    while left<=right:

        mid = (left+right)/2

        if li[mid] == val:

            return mid

        elif li[mid] >val:

            right = mid -1

        else:

            left = mid + 1

    else:

        return None

def bubble_sort(li):

    for i in range(len(li)-1):# n-1趟

        for j in range(len(li)-i-1): # 每一次内部循环需要比较的次数

            #

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

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

        print(li,f'第{i+1}次外部循环 ，内部循环比较次数{len(li)-i-1}')

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

bubble_sort(li)

def bubble_sort(li):

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

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

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

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

                # t=li[j]

                # li[j]=li[j+1]

                # li[j+1]=t

import random

# 列表生成式 L = [x * x for x in range(10)]  生成一个list,长度为1000，里面的元素是可以重复的随机数（范围0-10000）

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

print(li)

bubble_sort(li)

print(li)

def select_sort(li):

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

        min = i

        for j in range(min+1,len(li)):

            if li[min]>li[j]:

                li[min],li[j] = li[j],li[min]

        print(li, f'第{i+1}次外部循环 ，内部循环比较次数{len(li)-min-1}')

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

select_sort(li)

print(li)

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

def select_sort_simple(li):

    li_new = []

    for i in range(len(li)):

        min_val = min(li)

        li_new.append(min_val)

        li.remove(min_val)

    return li_new

print('select_sort_simple',select_sort_simple(li))

def select_sort(li):

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

        min_loc = i

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

            if li[j] < li[min_loc]:

                min_loc = j

        li[i],li[min_loc] = li[min_loc],li[i]

        print(li)

select_sort(li)

def insert_sort(li):

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

        tem = li[i]  # 要插入的数

        j = i-1 # j指的是手里的牌的下标

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

            li[j+1] = li[j]

            j -= 1

        li[j+1] = tem

        print(li)

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

insert_sort(li)

print(li,'最后结果')