python 常见排序算法

1.冒泡排序

对数组中每个位置的数据，从后往前推，依次比较相邻的两个数，如果后面的数较小，则交换两者位置，如果一次遍历没有发生任何数据交换，则排序直接完成。

def bubble_sort(li):
    le = len(li)
    for i in range(0, le):
        lee = le - i - 1
        for j in range(0, lee):

            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
       
    print(li)

2.选择排序

对数组中每个位置的数据，从后往前推，依次比较相邻的两个数，如果后面的数较大，则交换两者位置，如果一次遍历没有发生任何数据交换，则排序直接完成。

def select_sort(li):
    # 从第0位开始排序，直到最后一位（最后一位无需再排序）
    for i in range(len(li)-1):
        # 记录当前位置，作为对比的关键元素
        min_loc = i
        # 依次遍历后面的元素
        for j in range(i+1, len(li)):
            # 如果元素比关键元素小，则将关键元素位置指向此位置，再继续遍历
            if li[min_loc] > li[j]:
                min_loc = j

        # 遍历结束后，得到最小元素位置j，如果不是初始位置，则交换2个位置的值
        if i != min_loc:
            li[min_loc], li[i] = li[i], li[min_loc]
    
    print(li)

3.插入排序

从第1位开始，依次将数组分成2部分：前一部分可以视为已经排好序的，后一部分是未排序的,对后一部分的数据依次遍历，插入到前一部分中的合适位置

def insert_sort(li):
    if len(li) == 0:
        return None
    for i in range(len(li)):
        j = i
        # 待排序的数（是未排序部分的第1个数，它的上一位数就是已经排序的部分的最后一位数）
        temp = li[i]
        # 从已排序部分的最后一位开始依次往前推，如果比待排序的数大，则将其位置往后移一位
        while j > 0 and li[j-1] > temp:
            li[j] = li[j-1]
            j -= 1
        # 循环结束后的j即为待排序的数需要插入的位置
        li[j] = temp

4.快速排序

任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，再分别对两边的数据进行快速排序。

def quick_sort(li):
    l = len(li)

    if l == 0:
        return

    quick_sort_code(li, 0, l -1)

    print(li)


def quick_sort_code(li, start, end):
    if start > end:
        # 低位大于高位，排序结束
        return
    low = start
    high = end
    # 取第一个数作为关键数据
    key = li[start]

    while low < high:
        # 从后往前推，直到找到第一个比关键数据小的值
        while li[high] >= key and low < high:
            high -= 1

        # 将这个值与关键数据对调（关键数据处于low位置
        # 对调完关键数据处于high位置
        li[low], li[high] = li[high], li[low]

        while li[low] <= key and low < high:
            low += 1
        # 将这个值与关键数据（关键数据已经处于high位置）对调
        # 对调完关键数据处于low位置
        li[low], li[high] = li[high], li[low]

    # 对关键数据前面的数据进行快速排序
    quick_sort_code(li, start, low-1)

    # 对关键数据后面的数据进行快速排序
    quick_sort_code(li, low + 1, end)

5.二分法查找

def binary_search(li, val):
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = (low + high) // 2
        if li[mid] > val:
            high = mid - 1
        elif li[mid] < val:
            low = mid + 1
        else:
            return None
    else:
        return None