python列表查询、冒泡排序、快速排序、堆排序

列表查询:

def bin_search(data_set, val):
    low = 0
    high = len(data_set) - 1
    while low <= high:
        mid = (low + high) // 2
        if data_set[mid] == val:
            return mid
        elif data_set[mid] < val:  # val在右边
            low = mid + 1
        else:  # val在左边
            high = mid - 1
    return  # 没找到

冒泡排序:

def bubble_sort(li):
    for i in range(len(li) - 1):
        exchange = False
        for j in range(len(li) - i - 1):
            # 升序排列
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        if not exchange:
            break

选择排序:

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
        if min_loc != i:
            li[i], li[min_loc] = li[min_loc], li[i]

插入排序:

思路: 每次从无序区选择一个元素, 插入到有序区的位置, 直到无序区变空

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

快速排序:

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:
        # 从右边开始找, 找到比tmp小的, 就移到最左边
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        # 最左边的空位填上后, 从左开始找, 找到比tmp大的, 就移到右边的空位
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    # 左右重合
    data[left] = tmp
    return left

堆排序:

# 构造堆
def sift(data, low, high):
    i = low  # root
    j = 2*i+1  # left child
    tmp = data[i]
    while j <= high:  # not the end of child tree
        if j < high and data[j] < data[j+1]:  # j<high: have right child
            j += 1
        if tmp < data[j]:  # tmp not at right place
            data[i] = data[j]  # tmp get down
            i = j
            j = 2*i+1
        else:
            break
    data[i] = tmp