|
1 2 3 4 5 6 7 8 9 10 11 12 |
def insert_sort(ary): n=len(ary) for i in range(1,n): temp=ary[i] for j in range(i-1,-1,-1): if temp<ary[j]: print 'keep moving and move back one for the j' ary[j+1]=ary[j] ary[j]=temp else: break return ary |
代码参考地址：http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/#comments
插入排序关键点在于比较新的元素与已经完成排序的末尾数据，例如
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语句中，也就没有办法赋值，简单的解决方式就是，每次都赋值，就是我们上边的方法了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def insert_sort2(ary): print 'the origin is :' print ary n=len(ary) for i in range(1,n): temp=ary[i] index=i print 'The i is :% s' % i for j in range(i-1,-1,-1): if temp<ary[j]: print 'keep moving and move back one for the j' ary[j+1]=ary[j] #ary[j]=temp index=j else: ary[index]=temp break if index==0: ary[index]=temp #print ary return ary |
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021