Python 中的插入排序

与以前的冒泡排序算法相比,插入排序是一种简单且更有效的算法。插入排序算法的概念是基于一副牌,我们根据特定的牌排序扑克牌。它有很多优点,但是在数据结构中有很多有效的算法。

打牌的时候,我们互相比较手中的牌。大多数玩家喜欢按升序排序卡片,这样他们就可以很快看到他们可以使用的组合。

插入排序实现既简单又容易,因为它通常在编程入门课中讲授。是一个原位和稳定算法更有利于接近排序或更少的元素。

插入排序算法没有那么快,因为它使用嵌套循环排序元素。

让我们理解以下术语。

  • 原地:原地算法需要额外的空间,而不考虑集合的输入大小。执行排序后,它会重写集合中元素的原始内存位置。
  • Stable:Stable 是管理初始数组中相等对象的相对顺序的术语。

更重要的是,插入排序不需要预先知道数组大小,它一次接收一个元素。

插入排序的好处是,如果我们插入更多要排序的元素,算法会在适当的位置排列,而不执行完整的排序。

对于小(小于 10)尺寸的阵列来说,效率更高。现在,让我们理解插入排序的概念。

数组实际上溢出到插入排序中的两个部分-未排序的部分和排序的部分。

排序后的部分包含数组的第一个元素,其他未排序的子部分包含数组的其余部分。未排序数组中的第一个元素与排序数组进行比较,这样我们就可以将它放入适当的子数组中。

如果右侧值小于左侧值,它将通过移动所有元素来插入元素。

它将重复发生,直到将 all 元素插入到正确的位置。

使用插入排序排序数组下面是插入排序的算法。

  • 将列表分成两部分-已排序和未排序。
  • 在给定数组上从 arr[1]迭代到 arr[n]。
  • 将当前元素与下一个元素进行比较。
  • 如果当前元素小于下一个元素,与之前的元素进行比较,将较大的元素上移一个位置,为交换的元素腾出空间。

让我们理解下面的例子。

我们将在下面的数组中考虑排序数组中的第一个元素。

[10, 4, 25, 1, 5]

第一步向排序后的子阵列添加 10 个

[ 10 ,4,25,1,5]

现在我们从未排序的数组- 4 中取出第一个元素。我们将这个值存储在一个新的变量 temp 中。现在,我们可以看到 10 > 4,然后我们向右移动 10,这将覆盖之前存储的 4。

[ 10 ,10,25,1,5](温度= 4)

这里的 4 小于排序子数组中的所有元素,所以我们在第一个索引位置插入它。

[ 4,10, 25,1,5]

我们在排序的子数组中有两个元素。

现在检查数字 25。我们已经将其保存到 temp 变量中。 25 > 10 和 25 > 4 然后我们将它放在第三个位置,并将其添加到排序的子数组中。

[ 4,10,25, 1,5]

我们再次检查数字 1。我们将其保存在温度下。 1 小于 25。它覆盖了 25。

[ 4,10,25, 25,5] 10 > 1 然后再次覆盖

[ 4,25,10, 25,5]

[ 25,4,10, 25,5] 4 > 1 现在将 temp 的值设为 1

[ 1,4,10,25 ,5]

现在,我们在排序的子数组中有 4 个元素。左侧 5 <25 then shift 25 to the right side and pass 温度= 5 。

[ 1,4,10,25 ,25】放入温度= 5

现在,我们通过简单地放入临时值来得到排序的数组。

【1、4、5、10、25】

给定数组已排序。

插入的实现相对容易。我们将使用 Python 整数数组来实现。让我们理解下面的例子-

Python 程序


# creating a function for insertion
def insertion_sort(list1):

        # Outer loop to traverse through 1 to len(list1)
        for i in range(1, len(list1)):

            value = list1[i]

            # Move elements of list1[0..i-1], that are
            # greater than value, to one position ahead
            # of their current position
            j = i - 1
            while j >= 0 and value < list1[j]:
                list1[j + 1] = list1[j]
                j -= 1
            list1[j + 1] = value
        return list1
            # Driver code to test above

list1 = [10, 5, 13, 8, 2]
print("The unsorted list is:", list1)

print("The sorted list1 is:", insertion_sort(list1))

输出:

The unsorted list is: [10, 5, 13, 8, 2]
The sorted list1 is: [2, 5, 8, 10, 13]

说明:

在上面的代码中,我们创建了一个名为insert _ sort(list 1)的函数。在功能内部-

  • 我们定义了从 1 到 len(列表 1)遍历列表的循环。
  • for循环中,在值中赋值 list1 的值,每次循环迭代时,新值将赋给值变量。
  • 接下来,我们将列表 1[0…i-1]中大于值的元素移动到它们当前位置之前的一个位置。
  • 现在,我们使用 while 来检查 j 是否大于或等于 0,并且值小于列表的第一个元素。
  • 如果两个条件都成立,那么将第一个元素移动到第 0 个索引,并减少 j 的值,以此类推。
  • 之后,我们调用函数,传递列表并打印结果。

Python 提供了使用自定义对象更改算法的灵活性。我们将创建一个自定义类并重新定义实际的比较参数,并尝试保持与上面相同的代码。

我们需要重载操作符,以便以不同的方式排序对象。但是,我们可以通过使用λ函数将另一个参数传递给insert _ sort()函数。lambda 函数在调用排序方法时很方便。

让我们理解以下排序自定义对象的示例。

首先,我们定义点类:


# Creating Point class
class Point:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __str__(self):
        return str.format("({},{})", self.a, self.b)

def insertion_sort(list1, compare_function):
    for i in range(1, len(list1)):
        Value = list1[i]
        Position = i

        while Position > 0 and compare_function(list1[Position - 1], Value):
            list1[Position] = list1[Position - 1]
            Position = Position - 1

        list1[Position] = Value

U = Point(2,3)
V = Point(4,4)
X = Point(3,1)
Y = Point(8,0)
Z = Point(5,2)

list1 = [U,V,X,Y,Z]

# We sort by the x coordinate, ascending
insertion_sort(list1, lambda x, y: x.a > y.a)

for point in list1:
    print(point)

输出:

The points are in the sorted order
(2,3)
(3,1)
(4,4)
(5,2)
(8,0)

使用上面的代码,我们可以排序坐标点。它适用于任何类型的列表。

插入排序是一种缓慢的算法;有时,对于大规模数据集来说,这似乎太慢了。然而,它对于小列表或数组是有效的。

插入排序的时间复杂度为- O(n 2 )。使用两个循环进行迭代。

插入排序的另一个重要优点是:它被称为 Shell 排序的流行排序算法使用。

插入排序中的辅助空格: O(1)

插入排序是一种简单而低效的算法,它有很多优点,但也有更高效的算法可用。

在本教程中,我们讨论了插入排序的概念及其使用 Python 编程语言的实现。


原创文章,作者:NOMTP,如若转载,请注明出处:https://www.506064.com/n/127169.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
NOMTP的头像NOMTP
上一篇 2024-10-03 23:13
下一篇 2024-10-03 23:13

相关推荐

  • Python如何在文件系统中创建新的目录?

    一、使用os模块的mkdir函数创建新目录 在Python中,可以使用内置的os库来操作文件和目录。我们可以使用该模块中的mkdir函数来创建新目录。下面是示例代码: import…

    编程 2024-10-04
  • CSS淡入动画示例

    一、CSS淡入动画的意义 在互联网中,动画效果可以增加用户体验,使用户更容易记住网站,提高网站转化率。这种交互方式可以为用户提供更多的信息,并使网站变得更加生动。CSS淡入动画是一…

    编程 2024-11-12
  • 深入理解Python多线程假的

    一、什么是Python多线程 Python多线程是一种同时运行多个线程的编程技术。多线程可以提高程序的运行效率和吞吐量,以及提高程序的响应速度。Python多线程假的是指Pytho…

    编程 2024-10-03
  • python编写bmi计算器,Python计算BMI

    本文目录一览: 1、python新手简单程序出错求修改急求 2、Python小白一枚,自己写的BMI指数计算器,求教高手一下代码如何重复输入以及如何结束循环? 3、求一道Pytho…

    编程 2024-11-28
  • nginx版本号隐藏详解

    一、nginx隐藏版本号的两种方式 1、在nginx.conf的nginx配置文件里使用server_tokens关闭版本号 server_tokens off; 2、在编译安装n…

    编程 2024-12-03
  • 关于ios系统js后缀的信息

    本文目录一览: 1、手机怎么修改后缀是.js的文件 2、苹果 6s上的javascript是什么意思? 3、.js后缀的是什么文件 4、.js是什么文件格式 5、javascrip…

    编程 2024-12-11
  • Java结构体详解

    一、什么是Java结构体 Java结构体是一种用户自定义数据类型,它可以包含多个不同类型的数据成员,这些成员可以是基本数据类型、数组、对象等。结构体在Java语言中并不存在,但是可…

    编程 2024-11-25
  • 用Python的String Join方法快速串联字符串

    字符串是编程中广泛使用的一种数据类型。在Python中,也有各种各样的字符串操作方法。其中,String Join方法是一种能够快速串联字符串的高效方法,不仅能够提升代码的可读性,…

    编程 2024-12-05
  • atom的php插件(atom中文插件)

    本文目录一览: 1、atom插件频繁报错,怎么关闭错误信息提示 2、Atom汉化插件安装不上怎么办 3、使用atom 开发php需要装什么插件 4、Atom编辑器如何自动检查PHP…

  • Echarts坐标轴颜色详解

    Echarts是一个优秀的可视化库,可用于绘制各种各样的图表。其中坐标轴是图表中重要的组成部分之一。坐标轴颜色作为坐标轴外观的重要属性之一,为了更好地帮助开发者了解坐标轴颜色的配置…

    编程 2024-11-04

发表回复

登录后才能评论