冒泡排序，插入排序，快速排序

from typing import List
# 冒泡排序
def bubble_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return
    for i in range(length):
        made_swap = False
        for j in range(length - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                made_swap = True
        if not made_swap:
            break

# 插入排序
def insertion_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return
    for i in range(1, length):
        value = a[i]
        j = i - 1
        while j >= 0 and a[j] > value:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = value

# 选择排序
def selection_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return
    for i in range(length):
        min_index = i
        min_val = a[i]
        for j in range(i, length):
            if a[j] < min_val:
                min_val = a[j]
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

1.2编程实现O(n)时间复杂度内找到一组数据的第K大元素

#维护一个长度为k的堆

class KthLargest(object):

    def __init__(self, k, nums):
        self.k = k
        self.nums = sorted(nums)
        if len(self.nums) > k:
            self.nums = self.nums[-k:]

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.nums)<self.k:
            index = self.findIndex(val, self.nums, 0, len(self.nums) - 1)
            self.nums.insert(index, val)
        else:
            minh = self.nums[0]
            if val>minh:
                index = self.findIndex(val, self.nums, 0, len(self.nums) - 1)
                self.nums.insert(index, val)
                self.nums.pop(0)
        return self.nums[0]

    def findIndex(self, val, nums, start, end):
        if not nums:
            return 0
        if nums[start] >= val:
            return start
        elif nums[end] <= val:
            return end + 1
        mid = (start + end) // 2
        if nums[mid] == val:
            return mid
        elif nums[mid] < val:
            return self.findIndex(val, nums, mid + 1, end)
        else:
            return self.findIndex(val, nums, start, mid - 1)，

#2, 二分查找

2.1有序数组的二分查找

from typing import List

def bsearch(nums: List[int], target: int) -> int:
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1

2.2模糊二分查找（大于等于给定的第一个元素）

from typing import List

def bsearch_left(nums: List[int], target: int) -> int:
    """Binary search of the index of the first element
    equal to a given target in the ascending sorted array.
    If not found, return -1.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return low if nums[low] == target else -1