Python系列(21)—— 排序算法

简介: Python系列(21)—— 排序算法

Python中的排序算法

一、引言

排序算法是计算机科学中的基本算法之一,用于将一组数据按照特定的顺序进行排列。Python提供了多种排序算法的实现,包括内置的排序函数和手动实现的排序算法。本文将介绍几种常见的排序算法,并通过代码实例来展示它们的实现。

二、冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,通过重复遍历待排序的列表,比较相邻的元素并交换位置,直到列表有序为止。

代码实例

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标记,表示是否发生了交换
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换,说明列表已经有序,可以提前结束循环
        if not swapped:
            break
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的列表:", arr)

三、选择排序(Selection Sort)

选择排序通过每次从未排序的元素中选择最小(或最大)的元素,将其放置到已排序的序列的末尾(或开头),直到所有元素都排序完毕。

代码实例

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序部分中的最小元素
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 将最小元素交换到已排序部分的末尾
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("排序后的列表:", arr)

四、插入排序(Insertion Sort)

插入排序通过将未排序的元素一个个插入到已排序的序列中,从而得到有序序列。

代码实例

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        # 将大于key的元素向右移动
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("排序后的列表:", arr)

五、快速排序(Quick Sort)

快速排序是一种分而治之的排序算法,通过选择一个基准元素,将列表分为两个子列表,一个包含小于基准的元素,另一个包含大于基准的元素,然后递归地对子列表进行排序。

代码实例

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的列表:", sorted_arr)

六、归并排序(Merge Sort)

归并排序也是一种分而治之的排序算法,它将一个列表分成两个等长(几乎等长)的子列表,递归地对子列表进行排序,然后将排序后的子列表合并成一个有序的列表。

代码实例

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    return merge(left_half, right_half)
def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0
    # 合并两个已排序的列表
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    # 将剩余的元素添加到结果列表中
    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1
    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1
    return merged
# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("排序后的列表:", sorted_arr)

七、总结

本文介绍了Python中几种常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序,并通过代码实例展示了它们的实现。这些排序算法在不同的情况下各有优缺点,例如冒泡排序和选择排序对于小规模数据是有效的,但对于大规模数据效率较低。快速排序和归并排序在处理大规模数据时表现出色,但快速排序在最坏情况下的时间复杂度为O ( n 2 ) O(n^2)O(n2),而归并排序的时间复杂度始终为O ( n l o g n ) O(nlogn)O(nlogn)。了解这些算法的特点和适用场景,可以帮助你根据具体问题选择合适的排序算法。

目录
打赏
0
0
0
0
52
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
141 5
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
365 55
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
27 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
31 9
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
133 66
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
31 10
|
27天前
|
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
53 17
员工电脑监控屏幕场景下 Python 哈希表算法的探索
在数字化办公时代,员工电脑监控屏幕是保障信息安全和提升效率的重要手段。本文探讨哈希表算法在该场景中的应用,通过Python代码例程展示如何使用哈希表存储和查询员工操作记录,并结合数据库实现数据持久化,助力企业打造高效、安全的办公环境。哈希表在快速检索员工信息、优化系统性能方面发挥关键作用,为企业管理提供有力支持。
46 20

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等