level 7
blushadow
楼主
多谢大家的支持。先发一个话题，大家再给看看这种连载有多大意义。还请大家多提意见哈。
当初想起做这个连载的原因就是自己曾经在看语言书的时候发现，书上的程序大多枯燥无味，牵扯的算法应用力度也有限。前阵子去中关村图书大厦转了一圈，随便翻翻，发现多年来没啥大变化－－例子还是那样的例子，只是换个包装而已。著名的“算法导论”还算不错的，但谁又有多少时间能啃下那种东西呢？
于是，打算用些时间写写一些信息学奥林匹克竞赛中常用的强劲算法，让初学者也能体会计算机算法包含的技术与艺术之美。也希望更有经验的先行者以此为基础，分享更多有意义的算法知识。不敢奢望此举能改变编程人员的现状，至少，希望，在咱吧里，能掀起一下下学习基础科学的热情……
我是信息技术老师，教育是我的工作……
前言结束，正文开始。
信息学相关的算法很多，就从最简单、最常用的排序说起吧。
关于啥叫排序，不说了，直接上真格的－－本文都以小到大排序为例。
一、当需要排序的数据涵盖范围不大（注意，不是数据量不大，而是所有数据的涵盖范围不大）时，可以使用基于Hash的时间复杂度为O(n)的算法。我们知道，基于交换的算法，最低的时间复杂度是O(n*log(2,n))，在满足前述条件的情况之下，这种算法可以快很多。
代码如下：
OptionExplicit
'下面的Hash是标志数组，Hash(i)的值表示在数据中i出现了多少次
'我假定所有的数据都在1~1000之间
Dimn As Integer, d() As Integer, Hash(1000) As Integer
PrivateSub Form_Load()
Dimi As Integer, t As Integer, j As Integer
Open"d:\input.txt" For Input As #1
Open"d:\output.txt" For Output As #2
Input#1, n
ReDimd(n) As Integer
Fori = 1 To n
Input#1, t '读个数进来
Hash(t)= Hash(t) + 1 't对应的计数器加一个
Nexti
Fori = 0 To 1000
Forj = 1 To Hash(i)
Print#2, i;
Nextj
Nexti
Print#2, '空换行
Close
End
EndSub
可以看出，排序部分没有双重循环。输出部分虽然是双重循环，但print的执行次数是n次，这是一种明显的用空间换取时间的算法。在数据范围不大时非常有效。
d:\input.txt的内容如下：
10
2 78 1 3 4 2 15 24 2
二、如果给出的数据没有（一）中的条件，那么，用刚才的算法就行不通了。我们需要想其它的办法。如果数据量不太大（这里是数据量），比如1000个之内吧。传说中的冒泡排序还是挺好用的。虽然它是O(n^2)级别算法，但因为“数据量不大”嘛，时间上通常也能承受，关键是，它好写呀！！！！可以节省“开发成本”的……*^_^*
代码如下：
OptionExplicit
Dimn As Integer, d() As Integer
PrivateSub Form_Load()
Dimi As Integer, j As Integer, t As Integer
Open"d:\input.txt" For Input As #1
Open"d:\output.txt" For Output As #2
Input#1, n
ReDimd(n) As Integer
Fori = 1 To n
Input#1, d(i)
Nexti
Fori = 1 To n - 1
Forj = n To i + 1 Step -1
Ifd(j - 1) > d(j) Then
t= d(j - 1)
d(j- 1) = d(j)
d(j)= t
EndIf
Nextj
Nexti
Fori = 1 To n
Print
2011年03月14日 08点03分
1
当初想起做这个连载的原因就是自己曾经在看语言书的时候发现，书上的程序大多枯燥无味，牵扯的算法应用力度也有限。前阵子去中关村图书大厦转了一圈，随便翻翻，发现多年来没啥大变化－－例子还是那样的例子，只是换个包装而已。著名的“算法导论”还算不错的，但谁又有多少时间能啃下那种东西呢？
于是，打算用些时间写写一些信息学奥林匹克竞赛中常用的强劲算法，让初学者也能体会计算机算法包含的技术与艺术之美。也希望更有经验的先行者以此为基础，分享更多有意义的算法知识。不敢奢望此举能改变编程人员的现状，至少，希望，在咱吧里，能掀起一下下学习基础科学的热情……
我是信息技术老师，教育是我的工作……
前言结束，正文开始。
信息学相关的算法很多，就从最简单、最常用的排序说起吧。
关于啥叫排序，不说了，直接上真格的－－本文都以小到大排序为例。
一、当需要排序的数据涵盖范围不大（注意，不是数据量不大，而是所有数据的涵盖范围不大）时，可以使用基于Hash的时间复杂度为O(n)的算法。我们知道，基于交换的算法，最低的时间复杂度是O(n*log(2,n))，在满足前述条件的情况之下，这种算法可以快很多。
代码如下：
OptionExplicit
'下面的Hash是标志数组，Hash(i)的值表示在数据中i出现了多少次
'我假定所有的数据都在1~1000之间
Dimn As Integer, d() As Integer, Hash(1000) As Integer
PrivateSub Form_Load()
Dimi As Integer, t As Integer, j As Integer
Open"d:\input.txt" For Input As #1
Open"d:\output.txt" For Output As #2
Input#1, n
ReDimd(n) As Integer
Fori = 1 To n
Input#1, t '读个数进来
Hash(t)= Hash(t) + 1 't对应的计数器加一个
Nexti
Fori = 0 To 1000
Forj = 1 To Hash(i)
Print#2, i;
Nextj
Nexti
Print#2, '空换行
Close
End
EndSub
可以看出，排序部分没有双重循环。输出部分虽然是双重循环，但print的执行次数是n次，这是一种明显的用空间换取时间的算法。在数据范围不大时非常有效。
d:\input.txt的内容如下：
10
2 78 1 3 4 2 15 24 2
二、如果给出的数据没有（一）中的条件，那么，用刚才的算法就行不通了。我们需要想其它的办法。如果数据量不太大（这里是数据量），比如1000个之内吧。传说中的冒泡排序还是挺好用的。虽然它是O(n^2)级别算法，但因为“数据量不大”嘛，时间上通常也能承受，关键是，它好写呀！！！！可以节省“开发成本”的……*^_^*
代码如下：
OptionExplicit
Dimn As Integer, d() As Integer
PrivateSub Form_Load()
Dimi As Integer, j As Integer, t As Integer
Open"d:\input.txt" For Input As #1
Open"d:\output.txt" For Output As #2
Input#1, n
ReDimd(n) As Integer
Fori = 1 To n
Input#1, d(i)
Nexti
Fori = 1 To n - 1
Forj = n To i + 1 Step -1
Ifd(j - 1) > d(j) Then
t= d(j - 1)
d(j- 1) = d(j)
d(j)= t
EndIf
Nextj
Nexti
Fori = 1 To n
![[傻笑]](/static/emoticons/u50bbu7b11.png)
![[瀑布汗~]](/static/emoticons/u7011u5e03u6c57~.png)
算法这东西,看得我一个头两个大.
