Python学习笔记19（算法），,1.二分查找只能用二

Python学习笔记19（算法），,1.二分查找只能用二

1.二分查找

只能用二分查找查找有序列表

def bin_search(data,val):  #data为被查找的列表，val是要查找的值    low = 0    high = len(data) - 1    while low <= high:        mid = (low+high)//2        if data[mid] == val:            return mid           #找到了，返回val所在的索引        elif data[mid] < val:            low = mid + 1        else:            high = mid - 1    return                        #未找到，返回None

2.冒泡排序

def bubble_sort(data):                   #data传需要排序的列表    for i in range(len(data)-1):        FLAG = 0        for j in range(len(data)-i-1):            if data[j] > data[j+1]:                data[j],data[j+1] = data[j+1],data[j]                FLAG = 1        if FLAG == 0:            break

3.选择排序

def select_sort(data):    for i in range(len(data)-1):        min = i        for j in range(i+1,len(data)):            if data[j] < data[min]:                min = j        data[i],data[min] = data[min],data[i]

4.插入排序

def insert_sort(data):    for i in range(1,len(data)):        tmp = data[i]        j = i - 1        while j >= 0 and data[j] > tmp:            data[j+1] = data[j]            j = j - 1        data[j + 1] = tmp

5.快速排序

def quick_sort(data,left,right):    if left < right:        mid = partition(data,left,right)        quick_sort(data,left,mid - 1)        quick_sort(data,mid + 1,right)def partition(data,left,right):    tmp = data[left]    while left < right:        while left < right and data[right] >= tmp:            right -= 1        data[left] = data[right]        while left < right and data[left] <= tmp:            left += 1        data[right] = data[left]    data[left] = tmp    return left

6.堆排序

def sift(data,low,high):    i = low    j = 2 * i +1    tmp = data[i]    while j <= high:        if j + 1 <= high and data[j] < data[j+1]:            j += 1        if data[j] > tmp:            data[i] = data[j]            i = j            j = 2 * i + 1        else:            break    data[i] = tmpdef heap_sort(data):    n = len(data)    for i in range(n // 2 - 1 ,-1 ,-1):        sift(data,i,n-1)    for i in range(n-1,-1,-1):        data[0],data[i] = data[i],data[0]        sift(data,0,i-1)

7.归并排序

def merge(data,low,mid,high):    i = low    j = mid+1    tmp = []    while i <= mid and j <= high:        if data[i] < data[j]:            tmp.append(data[i])            i += 1        else:            tmp.append(data[j])            j += 1    while i <= mid:        tmp.append(data[i])        i += 1    while j <= high:        tmp.append(data[j])        j += 1    data[low:high+1] = tmpdef mergesort(data,low,high):    if low < high:        mid = (low+high)//2        mergesort(data,low,mid)        mergesort(data,mid+1,high)        merge(data,low,mid,high)

Python学习笔记19（算法）