算法-插入排序
插入排序实现
以下是插入排序的Python实现。
让我们来一步步地讲解。我会先摘出代码片段,然后给出解释。
首先,发起一个从索引1开始的循环来遍历数组。变量index保存的是当前索引。
然后在内部发起一个while循环,以检查position左侧的值是否大于temp_value。若是,则用array[position]=array[position -1]将该值右移一格,并将position减1。然后继续检查新position左侧的值是否大于temp_value……如此重复,直至遇到的值比temp_value小。
最后,将temp_value放回到数组的空隙中。
插入排序效率分析
插入排序包含4种步骤:移除、比较、平移和插入。要分析插入算法的效率,就得把每种步骤都统计一遍。
首先看看比较。每次拿temp_value跟空隙左侧的值比大小就是比较。
在数组完全逆序的最坏情况下,我们每一轮都要将temp_value左侧的所有值与temp_value比较。因为那些值全都大于temp_value,所以每一轮都要等到空隙移到最左端才能结束。
在第一轮,temp_value为索引1的值,由于temp_value左侧只有一个值,所以最多进行一次比较。到了第二轮,最多进行两次比较,以此类推。到最后一轮时,就要拿temp_value以外的所有值与其进行比较。换言之,如果数组有个元素,则最后一轮中最多进行 -1次比较。
因而可以得出比较的总次数为:
1 + 2 + 3 + … + -1次。
对于有5个元素的数组,最多需要:
1 + 2 + 3 + 4=10次比较。
对于有10个元素的数组,最多需要:1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9=45次比较。
(对于有20个元素的数组,最多需要190次比较,以此类推。)
由此可发现一个规律:对于有个元素的数组,大约需要/ 2次比较(102/ 2是50,202/ 2是200)。
接下来看看其他几种步骤。
我们每次将值右移一格,就是平移操作。当数组完全逆序时,有多少次比较就要多少次平移,因为每次比较的结果都会使你将值右移。
把最坏情况下的比较步数和平移步数相加。
/ 2次比较+ / 2次平移=步
temp_value的移除跟插入在每一轮里都会各发生一次。因为总是有 -1轮,所以可以得出结论:有 -1次移除和 -1次插入。把它们都相加。比较和平移的合计+ -1次移除+ -1次插入=+ 2 -2步。
我们已经知道大O有一条重要规则——忽略常数,于是你可能会将其简化成O(+ )。不过,现在来学习一下大O的另一条重要规则:大O只保留最高阶的。
换句话说,如果有个算法需要+ + + 步,我们就只会关注其中的,即以O()来表示。为什么呢?请看下表。
随着的变大,的增长越来越抛离其他阶。当为1000时,就比大了1000倍。因此,我们只关心最高阶的。
所以在插入排序的例子中,O(+ )还得进一步简化成O()。你会发现,在最坏的情况里,插入排序的时间复杂度跟冒泡排序、选择排序一样,都是O()。不过之前文章中指出,虽然冒泡排序和选择排序都是O(),但选择排序实际上是/ 2步,比步的冒泡排序更快。乍一看,你可能会觉得插入排序跟冒泡排序一样,因为它们都是O(),其实插入排序是+ 2 -2步。