Python教程:使用Python实现冒泡排序和快速排序

简介: 排序算法根据其实现原理和效率可以分为多种类型,包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。这些算法在不同的场景下具有不同的优劣势,需要根据实际需求选择合适的算法。

 1.冒泡排序


1.1介绍

冒泡排序(Bubble Sort)是一种简单直观的排序算法,它重复地遍历待排序序列,每次比较相邻的两个元素,如果它们的顺序错误就交换它们。经过一轮的遍历,最大(或最小)的元素就像气泡一样“冒”到了最后,因此得名冒泡排序。

1.2冒泡排序算法的原理

冒泡排序算法的基本原理如下:

  1. 从第一个元素开始,依次比较相邻的两个元素,如果顺序不正确则交换它们。
  2. 经过第一轮遍历后,最大(或最小)的元素被“冒泡”到了最后一个位置。
  3. 重复以上步骤,每次遍历都会将剩余未排序部分的最大(或最小)元素“冒泡”到合适的位置。
  4. 直到所有元素都排好序为止。

1.3Python 实现冒泡排序算法

下面是用 Python 实现冒泡排序算法的代码:

def bubble_sort(arr):
    n = len(arr)
    # 外层循环控制遍历次数
    for i in range(n - 1):
        # 内层循环进行相邻元素比较和交换
        for j in range(n - i - 1):
            # 如果前一个元素大于后一个元素,则交换它们
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)  # 输出: [11, 12, 22, 25, 34, 64, 90]

image.gif

2.快速排序


2.1介绍

快速排序(Quick Sort)是一种高效的排序算法,由英国计算机科学家 Tony Hoare 在 1960 年提出。它是一种分治算法,通过选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后对子数组递归地应用快速排序算法,最终使整个数组有序。

2.2 快速排序算法的原理

快速排序算法的基本原理如下:

  1. 选择一个基准元素(通常选择数组的第一个元素)。
  2. 使用两个指针,一个从数组的起始位置向后移动(称为左指针),一个从数组的末尾向前移动(称为右指针)。
  3. 左指针不断向右移动,直到找到一个大于基准元素的元素,右指针不断向左移动,直到找到一个小于基准元素的元素。
  4. 如果左指针小于等于右指针,则交换它们所指向的元素,并继续移动指针;否则,停止移动。
  5. 重复以上步骤,直到左指针超过右指针。
  6. 将基准元素与右指针所指向的元素交换位置,此时基准元素左边的元素都小于等于基准元素,右边的元素都大于等于基准元素。
  7. 分别对基准元素左边和右边的子数组递归地应用快速排序算法。

2.3 Python 实现快速排序算法

下面是用 Python 实现快速排序算法的代码:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less_than_pivot = [x for x in arr[1:] if x <= pivot]
        greater_than_pivot = [x for x in arr[1:] if x > pivot]
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)  # 输出: [11, 12, 22, 25, 34, 64, 90]

image.gif


目录
相关文章
|
27天前
|
存储 Python
SciPy 教程 之 SciPy 稀疏矩阵 4
SciPy 教程之 SciPy 稀疏矩阵 4:介绍稀疏矩阵的概念、类型及其在科学计算中的应用。SciPy 的 `scipy.sparse` 模块提供了处理稀疏矩阵的工具,重点讲解了 CSC 和 CSR 两种格式,并通过示例演示了如何创建和操作 CSR 矩阵。
43 3
|
14天前
|
BI Python
SciPy 教程 之 Scipy 显著性检验 8
本教程介绍SciPy中显著性检验的应用,包括如何利用scipy.stats模块进行显著性检验,以判断样本与总体假设间的差异是否显著。通过示例代码展示了如何使用describe()函数获取数组的统计描述信息,如观测次数、最小最大值、均值、方差等。
24 1
|
15天前
|
Python
SciPy 教程 之 Scipy 显著性检验 6
显著性检验是统计学中用于判断样本与总体假设间是否存在显著差异的方法。SciPy的scipy.stats模块提供了执行显著性检验的工具,如T检验,用于比较两组数据的均值是否来自同一分布。通过ttest_ind()函数,可以获取两样本的t统计量和p值,进而判断差异是否显著。示例代码展示了如何使用该函数进行T检验并输出结果。
19 1
|
16天前
|
Python
SciPy 教程 之 Scipy 显著性检验 3
本教程介绍Scipy显著性检验,包括其基本概念、原理及应用。显著性检验用于判断样本与总体假设间的差异是否显著,是统计学中的重要工具。Scipy通过`scipy.stats`模块提供了相关功能,支持双边检验等方法。
24 1
|
19天前
|
机器学习/深度学习 Python
SciPy 教程 之 SciPy 插值 2
SciPy插值教程:介绍插值概念及其在数值分析中的应用,特别是在处理数据缺失时的插补和平滑数据集。SciPy的`scipy.interpolate`模块提供了强大的插值功能,如一维插值和样条插值。通过`UnivariateSpline()`函数,可以轻松实现单变量插值,示例代码展示了如何对非线性点进行插值计算。
23 3
|
21天前
|
机器学习/深度学习 数据处理 Python
SciPy 教程 之 SciPy 空间数据 4
本教程介绍了SciPy的空间数据处理功能,主要通过scipy.spatial模块实现。内容涵盖空间数据的基本概念、距离矩阵的定义及其在生物信息学中的应用,以及如何计算欧几里得距离。示例代码展示了如何使用SciPy计算两点间的欧几里得距离。
32 5
|
21天前
|
机器学习/深度学习 Python
SciPy 教程 之 SciPy 空间数据 6
本教程介绍了SciPy处理空间数据的方法,包括使用scipy.spatial模块进行点位置判断、最近点计算等内容。还详细讲解了距离矩阵的概念及其应用,如在生物信息学中表示蛋白质结构等。最后,通过实例演示了如何计算两点间的余弦距离。
27 3
|
20天前
|
机器学习/深度学习 数据处理 Python
SciPy 教程 之 SciPy 空间数据 7
本教程介绍了SciPy的空间数据处理功能,涵盖如何使用`scipy.spatial`模块进行点的位置判断、最近点计算等操作。还详细解释了距离矩阵的概念及其在生物信息学中的应用,以及汉明距离的定义和计算方法。示例代码展示了如何计算两个点之间的汉明距离。
26 1
|
22天前
|
搜索推荐 Python
快速排序的 Python 实践:从原理到优化,打造你的排序利器!
本文介绍了 Python 中的快速排序算法,从基本原理、实现代码到优化方法进行了详细探讨。快速排序采用分治策略,通过选择基准元素将数组分为两部分,递归排序。文章还对比了快速排序与冒泡排序的性能,展示了优化前后快速排序的差异。通过这些分析,帮助读者理解快速排序的优势及优化的重要性,从而在实际应用中选择合适的排序算法和优化策略,提升程序性能。
32 1
|
23天前
|
Python
SciPy 教程 之 SciPy 图结构 7
《SciPy 教程 之 SciPy 图结构 7》介绍了 SciPy 中处理图结构的方法。图是由节点和边组成的集合,用于表示对象及其之间的关系。scipy.sparse.csgraph 模块提供了多种图处理功能,如 `breadth_first_order()` 方法可按广度优先顺序遍历图。示例代码展示了如何使用该方法从给定的邻接矩阵中获取广度优先遍历的顺序。
28 2