二分查找，选择排序，快速排序，归并排序，冒泡排序-蒲公英云

二分查找，选择排序，快速排序，归并排序，冒泡排序

墨蓝 2023-01-23 10:55 65阅读 0赞

# 二分查找 平均时间复杂度logn
def bianryfind(list,item):
    low =0;
    high= len(list)-1
    while low <= high：
        mid = int((low+high)/2)
        guess= list[mid]
        if guess == item:
            return guess
        else if guess>item:
            high = mid-1
        else:
            low =mid+1
    return None
# 将数组元素按照从小到大的顺序排序，每次从数组中取出最小值
# 平均时间复杂度n^2
def getSmallestIndex(arr):
    min_value = arr[0]
    min_index = 0
    for i in range(1,len(arr)):
        if arr[i]<min_value:
            min_value = arr[i]
            min_index = i
    return min_index
def selectionFind(arr):
    newarr =[]
    for i in range(0,len(arr)):
        min_index = getSmallestIndex(arr)
        newarr.append(arr[min_index])
    return newarr
# 递归
# 快速排序，分而治之的策略
# 平均时间复杂度 nlogn
def quickSort(arr):
    if len(arr)<2:
        return arr;
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        print(less)
        greater = [i for i in arr[1:] if i> pivot]
        print(greater)
    return quickSort(less)+pivot+quickSort(greater)
#simplesort 把小的不断往前排
# 时间复杂度为n^2
def simplesort(arr):
    for i in range(len(arr)-1):
        for j in range(i,range(arr)):
            if arr[i]<arr[j]:
                temp = arr[i]
                arr[i]= arr[j]
                arr[j] = temp
    return arr
# mergesort nlogn
def mergesort(arr):
    if len(arr)<2:
        return arr
    else:
        mid = int(len(arr)/2)
        right = mergesort(arr[mid:])
        left = mergesort(arr[:mid])
    return merge(left,right)
#merge 合并两个已经排好序的列表，产生一个新的列表
def merge(left,right):
    newarr =[]
    i=0
    j=0
    #对两个列表中的元素进行对比，将最小的元素放到新的列表中
    while i < len(left) and j< len(right):
        if left[i]<right[j]:
            newarr.append(left[i])
            i+=1
        else:
            newarr.append(right[j])
            j+=1
    #此时left 或者right已经被添加完毕,将其全部加到newarr中
    newarr+=left[i:]
    newarr+=right[j:]
    return newarr