排序算法(1)

  1. 云栖社区>
  2. 博客>
  3. 正文

排序算法(1)

aizher8860 2007-01-30 16:54:00 浏览910
展开阅读全文
算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言。

在这里您可以了解到:

算法定义
伪代码的使用
算法的复杂性
算法设计策略
常用算法
这里所有的算法都以一种类似Pascal语言的伪代码描述,请参阅伪代码的使用。

新增内容

关于数论的算法——数论基本知识(May 6, 2001)
动态规划重新整理 (January 15, 2001)
图的深度优先遍历 (January 21, 2001)
图的广度优先遍历 (January 21, 2001)
图的拓扑排序 (January 21, 2001)

算法 Algorithm
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。

一个算法应该具有以下五个重要的特征:

1. 有穷性: 一个算法必须保证执行有限步之后结束;

2. 确切性: 算法的每一步骤必须有确切的定义;

3. 输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;

4. 输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;

5. 可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。

Did you know

Algorithm 一词的由来

Algorithm (算法)一词本身就十分有趣。初看起来,这个词好像是某人打算要写“Logarithm”(对数)一词但却把头四个字母写的前后颠倒了。这个词一直到 1957年之前在Webster's New World Dictionary(《韦氏新世界词典》)中还未出现,我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术),指的是用阿拉伯数字进 行算术运算的过程。在中世纪时,珠算家用算盘进行计算,而算术家用算术进行计算。中世纪之后,对这个词的起源已经拿不准了,早期的语言学家试图推断它的来 历,认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的,但另一些人则不同意这种说法,认为这个词是从“喀斯迪尔国王 Algor”派生而来的。最后,数学史学家发现了algorism(算术)一词的真实起源:它来源于著名的Persian Textbook(《波斯教科书》)的作者的名字Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm (约公元前825年)——从字面上看,这个名字的意思是“Ja'far 的父亲,Mohammed 和 Mûsâ 的儿子,Khowârizm 的本地人”。Khowârizm 是前苏联XИBA(基发) 的小城镇 。Al-Khowârizm 写了著名的书Kitab al jabr w'al-muqabala (《复原和化简的规则》);另一个词,“algebra”(代数),是从他的书的标题引出来的,尽管这本书实际上根本不是讲代数的。

逐渐 地,“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的,这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由 algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (《数学大全辞典》) ,给出了Algorithmus (算法)一词的如下定义:“在这个名称之下,组合了四种类型的算术计算的概念,即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ,在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。

1950 年左右,algorithm一词经常地同欧几里德算法(Euclid's algorithm)联系在一起。这个算法就是在欧几里德的《几何原本》(Euclid's Elements ,第VII卷,命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。

左上方的图片是Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm的肖像,点击该图片可以看见关于他的更详细的资料。

排序
Sorting
排序问题的输入是一个线性表,该线性表的元素属于一个偏序集;要求对该线性表的元素做某种重排,使得线性表中除表尾外的每个元素都小于等于(或大于等于)它的后继。

设R 为非空集合A上的二元关系,如果R满足自反性(对于每一个x∈A,(x,x)∈R ),反对称性((x,y)∈R∧(y,x)∈R→x=y )和传递性((x,y)∈R∧(y,x)∈R→(x,z)∈R),则称R为A上的偏序关系,记作≤。如果(x,y)∈R,则记作x≤y,读作“x小于等于 y”。存在偏序关系的集合A称为偏序集。

注意,这里的≤不是指数的大小,而是指在偏序关系中的顺序性。x≤y的含义是:按照这个序,x排 在y前面。根据不同的偏序定义,≤有不同的解释。例如整除关系是偏序关系≤,3≤6的含义是3整除6。大于或等于关系也是偏序关系,针对这个关系5≤4是 指在大于或等于关系中5排在4的前面,也就是说5比4大。

在实际应用中,经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记 录类型中有一个主键域key,key域的类型是某一个偏序集,记录的其他域称为卫星数据。比较线性表中的两个元素Li和Lj的大小,实际上是比较 Li.key和Lj.key的大小(这种比较当然也是偏序集中的比较)。举例而言,某公司的数据库里记 录了员工的数据,每一项纪录包括姓名,编号,年龄,工资等几个域,如果以编号为key域对员工记录排序,则是将员工记录按照编号排序;如果以工资为key 域对员工记录排序,则是将员工记录按照工资高低排序;如果以姓名为key域对员工记录排序,则是以员工姓名的汉语拼音按照字典顺序排序。

关于偏序集的具体概念和应用,请参见离散数学的相关资料。

如果一个排序算法利用输入的线性表在原地重排其中元素,而没有额外的内存开销,这种排序算法叫做原地置换排序算法(in place sort);如果排序后并不改变表中相同的元素原来的相对位置,那么这种排序算法叫做稳定排序算法(stable sort)。

排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类:

1. 内排序:待排序的表中记录个数较少,整个排序过程中所有的记录都可以保留在内存中;

2. 外排序:待排序的记录个数足够多,以至于他们必须存储在磁带、磁盘上组成外部文件,排序过程中需要多次访问外存。

内排序

待排序的表中记录个数较少,整个排序过程中所有的记录都可以保留在内存中,这样的排序叫做内排序。

请参阅:

排序问题的计算复杂性
比较排序算法
冒泡排序
选择排序
插入排序
快速排序
合并排序
Shell排序
堆排序
线性时间排序算法
计数排序
基数排序
桶排序

冒泡排序 Bubble Sort
最 简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们 要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不 对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在 作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处 理,它们已正确地排好序。这个算法可实现如下。

procedure Bubble_Sort(var L:List);
var
i,j:position;
begin
1 for i:=First(L) to Last(L)-1 do
2 for j:=First(L) to Last(L)-i do
3 if L[j]>L[j+1] then
4 swap(L[j],L[j+1]); //交换L[j]和L[j+1]
end;
上 述算法将较大的元素看作较重的气泡,每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L的第一个元素和最后一个元素的位置, swap(x,y)交换变量x,y的值。上述算法简单地将线性表的位置当作整数用for循环来处理,但实际上线性表可能用链表实现;而且上述算法将线性表 元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明,所有的算法都用这种简化方式表达。

容易看出该算法总共进行了n(n-1)/2次比较。如果swap过程消耗的时间不多的话,主要时间消耗在比较上,因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录,则Swap过程要消耗大量的时间,因此有必要分析swap执行的次数。

显 然算法Bubble_Sort在最坏情况下调用n(n-1)/2次Swap过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列L1=k1, k2,..,kn和L2=kn,kn-1,..,k1。我们知道,如果ki>kj,且ki在表中排在kj前面,则在冒泡法排序时必定要将kj换到 ki前面,即kj向前浮的过程中一定要穿过一次ki,这个过程要调用一次Swap。对于任意的两个元素ki和kj,不妨设ki>kj,或者在L1中 ki排在kj前面,或者L2在中ki排在kj前面,两者必居其一。因此对于任意的两个元素ki和kj,在对L1和L2排序时,总共需要将这两个元素对调一 次。n个元素中任取两个元素有Cn2 种取法,因此对于两个互逆序列进行排序,总共要调用Cn2 =n(n-1)/2次Swap,平均每个序列要调用n(n-1)/4次Swap。那么算法Bubble_Sort调用Swap的平均次数为n(n-1) /4。

可以对冒泡算法作一些改进,如果算法第二行的某次内循环没有进行元素交换,则说明排序工作已经完成,可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换,如果没有则终止外循环。

冒泡法的另一个改进版本是双向扫描冒泡法(Bi-Directional Bubble Sort)。设被排序的表中各元素键值序列为:

483 67 888 50 

网友评论

登录后评论
0/500
评论
aizher8860
+ 关注