python数据结构和算法

'''
1. 数据结构和算法
排序算法（冒泡和归并）和查找算法（顺序和折半）
'''


def bubble_sort(origin_items, comp=lambda x, y: x > y):
    """⾼质量冒泡排序(搅拌排序)"""
    items = origin_items[:]
    for i in range(len(items) - 1):
        swapped = False
        for j in range(len(items) - 1 - i):
            if comp(items[j], items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if swapped:
            swapped = False
            for j in range(len(items) - 2 - i, i, -1):
                if comp(items[j - 1], items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    swapped = True
        if not swapped:
            break
    return items


# 归并排序（分治法）
def merger_sort(items, comp=lambda x, y: x <= y):
    """归并排序"""
    if len(items) < 2:
        return items[:]
    mid = len(items) // 2
    left = merger_sort(items[:mid], comp)
    right = merger_sort(items[mid:], comp)
    # print(merge(left, right, comp))
    print("this is left and right.")
    print(left, right)
    return merge(left, right, comp)


def merge(item1, item2, comp):
    items = []
    idx1, idx2 = 0, 0
    while idx1 < len(item1) and idx2 < len(item2):
        if comp(item1[idx1], item2[idx2]):
            items.append(item1[idx1])
            idx1 += 1
        else:
            items.append(item2[idx2])
            idx2 += 1
    items += item1[idx1:]
    items += item2[idx2:]
    # print(items)

    return items


# 顺序查找
def seq_search(items, key):
    for index, num in enumerate(items):
        if num == key:
            return index
    return -1


# 折半查找  有序数组中查找某一特定元素的搜索算法。
def bin_search(items, key):
    start, end = 0, len(items) - 1
    while start < end:
        mid = (start + end) // 2
        if key > items[mid]:
            start = mid + 1
        elif key < items[mid]:
            end = mid - 1
        else:
            return mid
    return -1


if __name__ == "__main__":
    items_test = [2]
    ls = [34, 12, 12, 4, 98, 5, 6]
    # print(ls[:])
    print(merger_sort(ls))  # [4, 5, 6, 12, 12, 34, 98]

本文链接：https://www.jianshu.com/p/1bddf3bf67b4