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²),因此插入排序也并非首选方案。

目录
相关文章
|
1月前
|
测试技术 API Python
【10月更文挑战第1天】python知识点100篇系列(13)-几种方法让你的电脑一直在工作
【10月更文挑战第1天】 本文介绍了如何通过Python自动操作鼠标或键盘使电脑保持活跃状态,避免自动息屏。提供了三种方法:1) 使用PyAutoGUI,通过安装pip工具并执行`pip install pyautogui`安装,利用`moveRel()`方法定时移动鼠标;2) 使用Pymouse,通过`pip install pyuserinput`安装,采用`move()`方法移动鼠标绝对位置;3) 使用PyKeyboard,同样需安装pyuserinput,模拟键盘操作。文中推荐使用PyAutoGUI,因其功能丰富且文档详尽。
WK
|
22天前
|
Python
Python中format_map()方法
在Python中,`format_map()`方法用于使用字典格式化字符串。它接受一个字典作为参数,用字典中的键值对替换字符串中的占位符。此方法适用于从字典动态获取值的场景,尤其在处理大量替换值时更为清晰和方便。
WK
68 36
|
1月前
|
机器学习/深度学习 数据采集 数据挖掘
11种经典时间序列预测方法:理论、Python实现与应用
本文将总结11种经典的时间序列预测方法,并提供它们在Python中的实现示例。
64 2
11种经典时间序列预测方法:理论、Python实现与应用
|
12天前
|
搜索推荐 Python
快速排序的 Python 实践:从原理到优化,打造你的排序利器!
本文介绍了 Python 中的快速排序算法,从基本原理、实现代码到优化方法进行了详细探讨。快速排序采用分治策略,通过选择基准元素将数组分为两部分,递归排序。文章还对比了快速排序与冒泡排序的性能,展示了优化前后快速排序的差异。通过这些分析,帮助读者理解快速排序的优势及优化的重要性,从而在实际应用中选择合适的排序算法和优化策略,提升程序性能。
27 1
|
29天前
|
开发者 Python
Python中的魔法方法与运算符重载
在Python的奇妙世界里,魔法方法(Magic Methods)和运算符重载(Operator Overloading)是两个强大的特性,它们允许开发者以更自然、更直观的方式操作对象。本文将深入探讨这些概念,并通过实例展示如何利用它们来增强代码的可读性和表达力。
|
1月前
|
Python
Python中的push方法详解与实例
Python中的push方法详解与实例
|
1月前
|
存储 Python
python列表操作和方法
python列表操作和方法
30 1
|
1月前
|
Linux Python
Python获得本机本地ip地址的方法
【10月更文挑战第8天】 socket模块包含了丰富的函数和方法,可以获取主机的ip地址,例如gethostbyname方法可以根据主机名获取ip地址,gethostbyname_ex方法可以获得本机所有ip地址列表,也可以使用netifaces模块获取网卡信息。
39 0
|
1月前
|
SQL 安全 数据库
Python防止SQL注入攻击的方法
Python防止SQL注入攻击的方法
52 0
|
1月前
|
程序员 Python
Python中Lambda表达式的优缺点及使用场景
Python中Lambda表达式的优缺点及使用场景
22 0