Python 插入排序:原理、使用场景与实现方法

简介: 本文主要介绍了Python 插入排序:原理、使用场景与实现方法

引言

插入排序(Insertion Sort)是一种简单直观且易于理解的排序算法,其工作原理类似于我们手动整理扑克牌的过程。通过构建一个有序序列,每次从未排序部分中取出一个元素并将其插入到已排序序列的正确位置,直到整个序列有序。尽管在处理大规模数据时效率较低,但对于小规模数据或部分有序的数据集,插入排序表现出了较好的性能。

insertionSort.gif

一、插入排序原理

  1. 构建初始有序序列:首先将数组的第一个元素视为已排序序列。
  2. 逐个插入:从第二个元素开始,依次与已排序序列中的元素进行比较,找到合适的插入位置,并将其插入。
  3. 重复上述过程:继续对剩余未排序元素执行相同的操作,直至所有元素都已排序到位。

二、插入排序步骤详解

假设有一个无序数组[5, 3, 8, 6, 7, 2],按照插入排序的过程:

  1. 第一轮:

    • 数组的第一个元素默认为已排序部分,即[5]
    • 将第二个元素35进行比较,发现3小于5,所以将3插入到5之前,得到[3, 5]
  2. 第二轮:

    • 已排序部分为[3, 5]
    • 将第三个元素8与已排序部分的元素依次比较,无需移动,得到[3, 5, 8]
  3. 继续这个过程,直到所有元素都已排序。

三、插入排序代码实现

以下是一个简单的插入排序实现:

def insertion_sort(arr):
    n = len(arr)

    # 遍历数组中的每个元素
    for i in range(1, n):
        current = arr[i]
        j = i - 1

        # 将当前元素与其左侧的已排序元素进行比较和交换
        while j >= 0 and arr[j] > current:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = current

    return arr

四、插入排序的使用场景

  • 小规模数据集:对于数据量较小的情况,插入排序可以快速完成排序任务,尤其是当数据近乎有序时,其时间复杂度接近O(n)。
  • 在部分场景下的优化:例如,当待排序数据基本有序时,插入排序能有效减少元素之间的比较次数,从而提高排序效率。

插入排序的时间复杂度达到O(n²),因此插入排序也并非首选方案。

目录
相关文章
|
24天前
|
存储 并行计算 Java
Python读取.nc文件的方法与技术详解
本文介绍了Python中读取.nc(NetCDF)文件的两种方法:使用netCDF4和xarray库。netCDF4库通过`Dataset`函数打开文件,`variables`属性获取变量,再通过字典键读取数据。xarray库利用`open_dataset`打开文件,直接通过变量名访问数据。文中还涉及性能优化,如分块读取、使用Dask进行并行计算以及仅加载所需变量。注意文件路径、变量命名和数据类型,读取后记得关闭文件(netCDF4需显式关闭)。随着科学数据的增长,掌握高效处理.nc文件的技能至关重要。
67 0
|
24天前
|
缓存 算法 测试技术
Python中的装饰器:原理与实践
【2月更文挑战第29天】 在Python编程领域,装饰器是一种强大的工具,它允许我们在不修改原始函数代码的情况下,增加或修改函数的行为。本文将深入探讨Python装饰器的概念、实现原理以及实际应用,帮助读者掌握这一技术并在实际项目中灵活运用。
|
25天前
|
数据处理 Python
python进行二进制数据处理的方法
python进行二进制数据处理的方法
15 0
|
1天前
|
Python
python魔法方法如何应用
这个Python示例展示了类继承和方法重写。`Student`类继承自`Person`,并覆盖了`say_hello`方法。通过`super().__init__(name)`调用父类的`__init__`初始化`name`属性,`Student`添加了`age`属性,并在重写的`say_hello`中使用。创建`Student`实例`student`并调用其`say_hello`,输出定制的问候信息。
9 1
|
2天前
|
机器学习/深度学习 人工智能 算法
|
2天前
|
安全 Python
python字典的内置方法
Python字典主要方法包括:`keys()`(返回所有键)、`values()`(返回所有值)、`items()`(返回所有键值对)、`get()`(安全取值,键不存在时返回默认值)、`setdefault()`(设置默认值)、`update()`(合并字典)、`pop()`(删除并返回值)、`clear()`(清空字典)、`copy()`(浅拷贝)、`fromkeys()`(新建字典并设置默认值)、`popitem()`(随机删除键值对)。
6 0
|
11天前
|
存储 Python
python基础篇: 详解 Python 字典类型内置方法
python基础篇: 详解 Python 字典类型内置方法
23 1
|
14天前
|
Java 测试技术 Python
Python开启线程和线程池的方法
Python开启线程和线程池的方法
12 0
Python开启线程和线程池的方法
|
15天前
|
算法 Python
数据结构与算法 经典排序方法(Python)
数据结构与算法 经典排序方法(Python)
23 0
|
18天前
|
Python
Python random模块(获取随机数)常用方法和使用例子
`random`模块在Python中用于生成随机数。
19 0