二分、冒泡、快速、插入排序-蒲公英云

1.二分查找（折半查找）

找出有序数据中的中间元素，由中间元素将数据分成左右两部分，比较中间元素与待查找值的大小：如果相等，则查找成功；如果中间元素比查找元素值大，则继续在左侧重复该过程；如果中间元素比查找元素值小，则继续在右侧重复该过程；如此递归下去，直到成功找到或者查找完所有数据为止。

使用递归实现：

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
# 二分查找
# 使用递归实现
# 原始数据　value
# 待查找数据 key - 6
# 当前查找范围左侧数据对应下标值　left
# 当前查找范围右侧数据对应下标值　right
def binary(value, key, left, right):
    # 递归退出条件
    if left > right:
        # 查找结束－查找失败
        return -1
    # 获取中间元素对应下标
    middle = (left + right) // 2
    # 对比中间数据值与待查找值
    if value[middle] == key:
        # 查找成功, 返回对应下标值
        return middle
    elif value[middle] > key:
        # 中间数据值大于待查找值时
        # 继续在左侧重复该过程
        # 查找范围缩小：左侧不变，右侧变为中间元素的前一位
        return binary(value, key, left, middle-1)
    else:
        # 中间数据值小于待查找值时
        # 继续在右侧重复该过程
        # 查找范围缩小：左侧变为中间元素的后一位，右侧不变
        return binary(value, key, middle+1, right)
if __name__ == "__main__":
    # 原始数据　value
    value = [1,2,3,4,5,6,7,8,9,10,11,12,13]
    # 待查找数据 key 
    key = 6
    #　调用二分查找
    res = binary(value, key, 0, len(value)-1)
    if res == -1:
        print("查找失败")
    else:
        print("查找成功:", res)

使用循环实现：

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
# 二分查找
# 使用循环实现
# 原始数据　value
# 待查找数据 key - 6
def binary(value, key):
    # 获取左侧／右侧数据对应下标值
    left = 0
    right = len(value) - 1
    # 如果存在合法范围则继续
    while left <= right:
        # 获取中间数据对应下标值
        middle = (left + right) // 2
        # 比较中间数据值与待查找数据
        if value[middle] == key:
            # 中间数据值与待查找数据相等
            # 查找成功,返回对应下标值
            return middle
        elif value[middle] > key:
            # 中间数据值大于待查找数据时
            # 继续在左侧重复查找
            # 查找范围缩小：左侧不变，右侧变为中间的前一位
            right = middle - 1
        else:
            # 中间数据值小于待查找数据时
            # 继续在右侧重复查找
            # 查找范围缩小：右侧不变，左侧变为中间的后一位
            left = middle + 1
    # 查找失败，返回－１
    return -1
if __name__ == "__main__":
    # 原始数据　value
    value = [1,2,3,4,5,6,7,8,9,10,11,12,13]
    # 待查找数据 key 
    key = 6
    #　调用二分查找
    res = binary(value, key)
    if res == -1:
        print("查找失败")
    else:
        print("查找成功:", res)

2. 冒泡排序重复走访要排序的数据，依次对比每两个相邻的元素，如果次序错误则交换；重复进行直到没有相邻数据需要交换为止，此时完成排序

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
# 冒泡排序
# 原始数据 value
def bubble(value):
    # 外层循环：对应数据走访的次数
    for i in range(len(value) - 1):
        # 设置初始标识为的值，为False
        flag = False
        # 内层循环：对应每次走访数据时，相邻数据对比次数
        for j in range(len(value) - 1 - i):
            # 要求从小到大，如前者大于后者，则交换
            if value[j] > value[j+1]:
                value[j],value[j+1] = value[j+1],value[j]
                # 若数据发生交换，则置为True
                flag = True
        # 若当前走访数据时，未发生数据交换
        # 则当前数据有序，无需继续走访
        if flag is False:
            break
    # 打印走访次数
    print("走访次数", i+1)
if __name__ == "__main__":
    # 原始数据　
    # value = [180, 230, 149, 260, 130, 170, 160, 169, 163, 178]
    value = [350, 130, 149, 160, 163, 169, 170, 178, 180, 230, 260]
    print("原始数据：", value)
    # 调用排序
    bubble(value)
    print("排序后：", value)

3.插入排序

将数据插入到已经有序的部分中，从而得到新的有序数据。默认首元素自然有序，取下一个元素对已经有序的数据从后向前扫描：若扫描到的有序数据大于取出数据，则该有序数据后移；若扫描到的有序数据小于等于取出数据，则在该有序数据后面插入取出数据；若所有有序数据均大于取出数据，则有序数据首部插入取出数据。重复上步骤，直到处理完所有数据为止。

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
# 插入排序
# 原始数据
def insert(value):
    # 外层循环：对应遍历所有无序数据，依次取出元素
    for i in range(1, len(value)):
        # 取出当前无序数据
        temp = value[i]
        # 存储取出数据的插入位置（下标值）
        pos = i
        # 内层循环：对应从后向前扫描所有有序数据，找出插入数据的位置
        # start:从最后一个有序数据开始，即无序数据前一位
        # end:到有序数据首位终止，包含下标为０
        # step:从后向前扫描：-1
        for j in range(i-1, -1, -1):
            if value[j] > temp:
                # 有序数据大于取出数据
                # 有序数据后移
                value[j+1] = value[j]
                # 更新当前取出数据可插入位置
                pos = j
            else:
                # 有序数据小于等于取出数据
                # 在有序数据后插入取出数据
                # 有序数据的后一位
                pos = j + 1
                # 确定插入位置，退出内层循环
                break
        # 在指定的位置插入数据
        value[pos] = temp
if __name__ == "__main__":
    # 原始数据
    value = [99,20,85,70,30,18,100,13,76,98]
    print("原始数据：",value)
    # 调用排序
    insert(value)
    print("排序后：",value)

4.快速排序首先任意取一个数据（通常取第一个数据）作为关键数据，然后将所有比关键数据小的放在它的前面，所有比关键数据大的放在它的后面，这样的一个过程称为一趟快速排序。通过一趟快速排序，将所有数据分割成独立的两部分，然后按照这个方法递归对两部分数据进行快速排序，以达到所有数据有序。

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
#快速排序
# 原始数据
def quick(value):
    # 递归的退出条件
    # 仅有一个数据时无需继续排序
    if len(value) < 2:
        return value
    # 获取关键数据
    mark = value[0]
    # 找出所有比关键数据小的
    smaller = [x for x in value if x < mark]
    # 找出所有比关键数据大的
    bigger = [x for x in value if x > mark]
    # 找出所有与关键数据相等的
    eq = [x for x in value if x == mark]
    # 从小到大排序
    return quick(smaller) + eq + quick(bigger)
if __name__ == "__main__":
    # 原始数据
    value = [88,38,77,43,18,1,100,99,96,69]
    print("原始数据：", value)
    # 调用快速排序
    value = quick(value)
    print("排序后：", value)

5.顺序查找

从待查找数据中第一元素开始，逐个对每个元素值与要查找的内容进行对比，如果相等，则查找成功；如果到最后仍未找到则查找失败。

# -*- coding: utf-8 -*-
# @Author  : Codeooo
# @Time    : 2021/12/05
# 顺序查找
# 原始数据 value 
# [12, 10, 1, 3, 5, 9, 11, 6, 2, 4, 8, 7, 13]
# 待查找数据 key　- 7
def linear(value, key):
    # 获取所有数据
    for i in range(len(value)):
        # 对比取出数据与待查找数据
        if value[i] == key:
            # 查找成功,返回当前下标值
            return i
    # 查找完所有数据，仍未找到
    # 查找失败，返回非法下标值
    return -1
if __name__ == "__main__":
    # 原始数据 value 
    value = [12, 10, 1, 3, 5, 9, 11, 6, 2, 4, 8, 7, 13]
    # 待查找数据 key　- 7 
    key = 7
    # 调用查找函数
    res = linear(value, key)
    if res == -1:
        # 查找失败
        print("查找失败")
    else:
        # 查找成功
        print("查找成功：", res)
    print((0 + 11)// 2)
    print((3 + 4) // 2)