blushadow blushadow
关注数: 14 粉丝数: 37 发帖数: 1,154 关注贴吧数: 7
常用算法连载01 - 有关排序的话题 多谢大家的支持。先发一个话题,大家再给看看这种连载有多大意义。还请大家多提意见哈。 当初想起做这个连载的原因就是自己曾经在看语言书的时候发现,书上的程序大多枯燥无味,牵扯的算法应用力度也有限。前阵子去中关村图书大厦转了一圈,随便翻翻,发现多年来没啥大变化--例子还是那样的例子,只是换个包装而已。著名的“算法导论”还算不错的,但谁又有多少时间能啃下那种东西呢? 于是,打算用些时间写写一些信息学奥林匹克竞赛中常用的强劲算法,让初学者也能体会计算机算法包含的技术与艺术之美。也希望更有经验的先行者以此为基础,分享更多有意义的算法知识。不敢奢望此举能改变编程人员的现状,至少,希望,在咱吧里,能掀起一下下学习基础科学的热情…… 我是信息技术老师,教育是我的工作…… 前言结束,正文开始。 信息学相关的算法很多,就从最简单、最常用的排序说起吧。 关于啥叫排序,不说了,直接上真格的--本文都以小到大排序为例。 一、当需要排序的数据涵盖范围不大(注意,不是数据量不大,而是所有数据的涵盖范围不大)时,可以使用基于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
1 下一页