排序
排序是与搜索算法同等重要的基本算法的概念之一。有很多算法可以对项目进行排序。为什么我们需要对元素进行排序?因为一旦对元素进行排序,问题就会变得更加容易。例如,当对数组进行排序时,您可以在恒定时间内找到中值,这意味着您可以使用二进制搜索。
插入排序
如果您想到最容易在脑中进行排序的方式,则可能类似于插入排序。基本上,它的工作方式是从左到右交换成对的元素,直到它们被排序为止。我们将有一个称为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
我们换了9
,7
因为他们没有排序。因为7
和9
被排序,所以将键移到那里的右边4
。然后比较9
和4
。9
大于,4
但4
在左侧,则应交换它们。
4
向下 移动到左侧,直到将其排序。一对交换后,j
向左移动。在这种情况下,直到放置4为止arr[0]
(特别是在代码中,当j变为-1时)。然后将钥匙移到右边的位置5
。
现在,key = 5
我们需要进行排序,5
直到下降到为止arr[1]
,让我们开始。
因为键(4
)已排序,所以继续移动到元素,键变成1(arr[4]
)。继续交换直到排序为1。然后结果将如下所示。
插入排序的时间复杂度
现在,该讨论算法的时间复杂性了。您可能会想到,我们花了很长时间才到达这里。简而言之,算法为O(n²)。让我们分析一下原因。
如您所见,(2)* O(1)和(2)* O(N)和(2)* O(N)。我们实际上可以忽略该系数。因此,时间复杂度将为1 * N * N =N²
总之,插入的时间复杂度是二次时间,不是很有效。不过,有一种更快的方式对元素进行排序。稍后再介绍。谢谢阅读!
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 学习算法-插入排序
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 学习算法-插入排序
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。