首页 » python » 正文

python插入排序(动画演示)

代码参考地址:http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/#comments

 

220px-Insertion-sort-example-300px

 

插入排序关键点在于比较新的元素与已经完成排序的末尾数据,例如

12,43

我们新拿一个数据叫作9

第一次,我们用9和43对比,发现,9<43,那么,我们需要将数组中的arg[2]设置为43(arg[2]原来是9),a[1]我们则需要设置为9,我们得到了新的数组

12 9 43

但是这个时候我们并没有完,我们需要继续将我们的新元素9与12进行比较,发现还小

然后我们得到了 9 12 43

同理,17 < 43,我们将17与43互换位置

另外一种实现方式,是,我们需要额外定义一个要插入的下标

但是,这样有一个问题,就是我们如果只记录需要插入的下标的话,需要单独考虑下标=0的时候,因为如果是数组中最小的数进行对比,将永远符合 temp<arg[j],也就是说永远走不到else语句中,也就没有办法赋值,简单的解决方式就是,每次都赋值,就是我们上边的方法了

 

 

发表评论