ACE Developer

 找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 4793|回复: 0

排序算法——插入排序

[复制链接]
发表于 2012-2-24 14:53:13 | 显示全部楼层 |阅读模式
这个排序系列没有主要次要之分,也不按难易顺序,完全随机。今天先说说插入排序。
思想
插入排序的思想有点像打扑克抓牌的时候,我们插入扑克牌的做法。想象一下,抓牌时,我们都是把抓到的牌按顺序放在手中。因此每抓一张新牌,我们都将其插入到已有的排好序的手牌当中,注意体会刚才的那句话。也就是说,插入排序的思想是,将新来的元素按顺序放入一个已有的有序序列当中。
举个例子可能更容易理解一些,假设有这样一系列数字:
8 2 4 9 3 6  首先我们考虑数字2,假设后面的数字不存在(手中只有一张8,又抓来了2),那么显然2应该放在8的前面。
2 8 4 9 3 6  又抓来了一张4,现在大家都知道应该怎么办了吧?
2 4 8 9 3 6  又来了个9,没错,正好不用换顺序
2 4 8 9 3 6  同样的道理,考虑3该放的位置,显然放在2和4的中间
2 3 4 8 9 6  最后一个也是一样,最后得到从小到大的序列
2 3 4 6 8 9  完成排序
怎么样,这下全明白了吧,其实很简单。
代码
printline("before sort:", v);
        for (int i=1; i<v.size(); i++){
                int key = v;
                int j = i-1;
                while (j >= 0 && v[j] > key){
                        v[j+1] = v[j];
                        j--;
                }
                v[j+1] = key;

        }
        printline("after sort:", v);

代码中,key相当于每次要比较的元素。
分析
插入排序的思路很简单,很清晰,是一种最常见最简单的排序方法。但是可以看出,由于需要两层循环,外层循环n-1次,内层循环每次递增一次。当输入完全从小到大有序时,只需要常数的时间,这当然是最好的情况。但是我们不能期望输入,当输入完全逆序时,最坏的情况就出现了,显然时间复杂度是O(n*n)的。我们都很清楚,这个时间复杂度在排序中并不能算好的。这也是为什么插入排序虽然简单,但并没有被广泛应用的原因所在。

今天就到这里吧,吃饭去了。
本文链接

您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2022-5-17 18:42 , Processed in 0.014622 second(s), 8 queries , Redis On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表