美文网首页笔记本📒
python-冒泡排序-选择排序-插入排序-快速排序-二分查找

python-冒泡排序-选择排序-插入排序-快速排序-二分查找

作者: 涓涓自然卷 | 来源:发表于2021-01-28 16:45 被阅读0次

1、冒泡排序 - 实现列表[5, 3, 4, 7, 2]排序:

# 冒泡法实现列表排序
def bubble_sort(alist):
    """冒泡排序"""
    # 数列的长度
    n = len(alist)

    # 控制比较轮数
    for j in range(0, n - 1):
        # 计数
        count = 0
        # 控制每一轮的比较次数
        for i in range(0, n - j - 1):
            # 比较相邻的;两个数字,不符合要求交换位置
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                count += 1
        # 如果遍历一遍发现没有数字交换,退出循环,证明数列有序
        if count == 0:
            break


if __name__ == '__main__':
    alist = [5, 3, 4, 7, 2]
    bubble_sort(alist)
    print(alist)

  • 冒泡排序运行结果:
冒泡排序运行结果.png

2、选择排序 - 实现列表[1, 3, 4, 10, 0, 1000, 88]排序:

def select_sort(alist):
    """选择排序"""

    # 列表的长度
    n = len(alist)

    # 控制比价轮数
    for j in range(0, n - 1):
        # 假定的最小值的下标
        min_index = j

        # 控制比较次数
        for i in range(j + 1, n):
            # 进行比较获得最小值
            if alist[i] < alist[min_index]:
                min_index = i

        # 如果假定的最小值下标发生了变化,那么就进行交换
        if min_index != j:
            alist[j], alist[min_index] = alist[min_index], alist[j]


if __name__ == '__main__':
    alist = [1, 3, 4, 10, 0, 1000, 88]
    select_sort(alist)
    print(alist)

  • 选择排序运行结果:
选择排序运行结果.png

3、插入排序 - 实现列表[1, 100, 99, 20, 5, 1000]排序:

def insert_sort(alist):
    """插入排序"""
    # 列表的长度
    n = len(alist)

    # 控制轮数
    for j in range(1, n):
        # [j, j-1, j-2, ……,,1]
        # 找到合适的位置安放我们的无序的数据
        for i in range(j, 0, -1):
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
            else:
                break


if __name__ == '__main__':
    alist = [1, 100, 99, 20, 5, 1000]
    print("原来的列表:", alist)
    insert_sort(alist)
    print("排序后的列表:", alist)

  • 插入排序运行结果:
插入排序运行结果.png

4、快速排序 - 实现列表[1, 3, 100, 50, 1000, 0, 1, 1]排序:

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的结束条件
    if start >= end:
        return

    # 界限值
    mid = alist[start]
    # 左右游标
    left = start
    right = end

    while left < right:
        # 从右边开始找寻小于mid的值 归类到左边
        while alist[right] >= mid and left < right:
            right -= 1
        alist[left] = alist[right]
        # 从左边开始找寻大于mid的值 归类到左边
        while alist[left] < mid and left < right:
            left += 1
        alist[right] = alist[left]

    # 循环一旦结束了 证明找到了mid应该在的位置
    alist[left] = mid

    # 递归操作
    quick_sort(alist, start, left - 1)
    quick_sort(alist, right + 1, end)


if __name__ == '__main__':
    aist = [1, 3, 100, 50, 1000, 0, 1, 1]
    quick_sort(aist, 0, len(aist) - 1)
    print(aist)

  • 快速排序运行结果:
快速排序运行结果.png

5、二分查找(1)递归法 - 查找元素是否在列表[1, 3, 6, 31, 100]中:

def binary_search(alist, item):
    """二分查找"""

    # 获取数列的长度
    n = len(alist)
    # 递归的结束条件
    if n == 0:
        return False

    # 中间值
    mid = n // 2

    if item == alist[mid]:
        return True
    elif item < alist[mid]:
        return binary_search(alist[0:mid], item)
    elif item > alist[mid]:
        return binary_search(alist[mid + 1:], item)
    else:
        return False


if __name__ == '__main__':
    alist = [1, 3, 6, 31, 100]
    print('31是否在列表[1, 3, 6, 31, 100]:', binary_search(alist, 31))
    print('32是否在列表[1, 3, 6, 31, 100]:', binary_search(alist, 32))

 
  • 二分查找递归法运行结果:
二分查找递归法运行结果.png

6、二分查找(2)非递归法 - 查找元素是否在列表[1, 3, 6, 31, 100]中:

def binary_search(alist, item):
    """二分查找"""

    # 设置起始位置 获取中间值
    start = 0
    end = len(alist) - 1

    while start <= end:
        # 中间值
        mid = (start + end) // 2

        if item == alist[mid]:
            return True
        elif item < alist[mid]:
            end = mid - 1
        elif item > alist[mid]:
            start = mid + 1
    # 没有找到想要的数字
    return False


if __name__ == '__main__':
    alist = [1, 2, 3, 4, 5]
    print('1是否在列表[1, 2, 3, 4, 5]中:', binary_search(alist, 1))
    print('100是否在列表[1, 2, 3, 4, 5]中:', binary_search(alist, 100))

  • 二分查找非递归法运行结果:
二分查找非递归法运行结果:.png

相关文章

  • 18-04-27  python3 算法笔记 003查找与排序

    查找: 顺序查找 二分查找 hash查找 排序: 冒泡排序 选择排序 插入排序希尔排序 归并排序 快速...

  • 基础排序算法

    快速排序 二分查找 冒泡排序 归并算法 选择排序 插入排序 Shell排序

  • 基本算法

    冒泡排序、插入排序、选择排序、快速排序、二分查找(Objective-C实现)

  • PHP数组示例算法

    1、冒泡排序 2、归并排序 3、二分查找-递归 4、二分查找-非递归 5、快速排序 6、选择排序 7、插入排序

  • 排序(新排版)

    冒泡排序 插入排序 二分插入排序 希尔排序 选择排序 快速排序

  • 排序算法

    冒泡排序 选择排序 插入排序二分插入排序希尔排序 堆排序 归并排序 快速排序 交换排序类:冒泡排序快速排序 选择排...

  • 排序算法

    冒泡排序 堆排序 插入排序 二分法查找插入排序 希尔排序 快速排序 归并排序

  • 基本算法

    冒泡算法 选择排序 插入排序 顺序查找 二分查找

  • 面试知识点

    排序冒泡排序快速排序选择排序插入排序二路归并 查找二分查找 排序和查找的java实现 java语言Java字符串字...

  • Java实现常见的算法

    主要罗列了常见的选择排序,冒泡排序和快速排序,还有二分查找的算法。 选择排序 冒泡排序 快速排序 二分查找 注意二...

网友评论

    本文标题:python-冒泡排序-选择排序-插入排序-快速排序-二分查找

    本文链接:https://www.haomeiwen.com/subject/ffcxtltx.html