学习算法-插入排序

作者 : IT 大叔 本文共1192个字,预计阅读时间需要3分钟 发布时间: 2020-10-9

排序

排序是与搜索算法同等重要的基本算法的概念之一。有很多算法可以对项目进行排序。为什么我们需要对元素进行排序?因为一旦对元素进行排序,问题就会变得更加容易。例如,当对数组进行排序时,您可以在恒定时间内找到中值,这意味着您可以使用二进制搜索。

插入排序

如果您想到最容易在脑中进行排序的方式,则可能类似于插入排序。基本上,它的工作方式是从左到右交换成对的元素,直到它们被排序为止。我们将有一个称为key的指针,该指针从1开始。

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i

学习算法-插入排序插图
上面的代码看起来像这样。

将一直从1遍历到结尾(n),并j指向0(索引)。一次将移动到右侧左元素排序。该规则可以表示如下。

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
        # as long as j is greater than or equals to 0 and left 
        # element(arr[j]) of key is bigger than key, 

        while j >= 0 and arr[j] > key:
           # swap: its left item will move to key
           arr[j + 1] = arr[j]
           # j moves down to the left
           j = j - 1
        # once all sorted, move elements 
        # where j stopped lastly
        arr[j + 1] = key

学习算法-插入排序插图(2)
我们换了97因为他们没有排序。因为79被排序,所以将键移到那里的右边4。然后比较949大于,44左侧,则应交换它们。

学习算法-插入排序插图(4)
4向下 移动到左侧,直到将其排序。一对交换后,j向左移动。在这种情况下,直到放置4为止arr[0](特别是在代码中,当j变为-1时)。然后将钥匙移到右边的位置5

学习算法-插入排序插图(6)
现在,key = 5我们需要进行排序,5直到下降到为止arr[1],让我们开始。

学习算法-插入排序插图(8)

学习算法-插入排序插图(10)
因为4)已排序,所以继续移动到元素,键变成1arr[4])。继续交换直到排序为1。然后结果将如下所示。

学习算法-插入排序插图(12)
现在key = 3,我们将交换93

学习算法-插入排序插图(14)
继续进行相同的过程,直到3进入arr[1]

学习算法-插入排序插图(16)
最后,我们到了!数组中的所有元素均已排序

插入排序的时间复杂度

现在,该讨论算法的时间复杂性了。您可能会想到,我们花了很长时间才到达这里。简而言之,算法为O(n²)。让我们分析一下原因。

学习算法-插入排序插图(18)

如您所见,(2)* O(1)和(2)* O(N)和(2)* O(N)。我们实际上可以忽略该系数。因此,时间复杂度将为1 * N * N =N²

总之,插入的时间复杂度是二次时间,不是很有效。不过,有一种更快的方式对元素进行排序。稍后再介绍。谢谢阅读!

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 学习算法-插入排序

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论