二分、冒泡、快速、插入排序

清疚 2023-10-01 08:34 10阅读 0赞

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

![9de6676017b94a12b503d0344843bf0a.gif][]

# -*- 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.插入排序 ####

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

![c31aa91870f44460b3bfe741a04a5bbd.gif][]

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

![11224a46205044efbacca88c99cebb7b.gif][]

# -*- 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)

[9de6676017b94a12b503d0344843bf0a.gif]: https://img-blog.csdnimg.cn/9de6676017b94a12b503d0344843bf0a.gif
[c31aa91870f44460b3bfe741a04a5bbd.gif]: https://img-blog.csdnimg.cn/c31aa91870f44460b3bfe741a04a5bbd.gif
[11224a46205044efbacca88c99cebb7b.gif]: https://img-blog.csdnimg.cn/11224a46205044efbacca88c99cebb7b.gif