＋设为首页 ＋添加到收藏夹
排 序
【程序编程相关:多硬盘操作系统的引导】程序员可以使用的基本排序算法有5种: 【推荐阅读:破解本地的mysql用户名和密码】
【扩展信息:面试时最经常被问到的问题（Frenque】 ·插入排序(insertionsort．) ·交换排序(exchangesort) ·选择排序(selectionsort) ·归并排序(mergesort) ·分布排序(distributionsort)为了形象地解释每种排序算法是怎样工作的,让我们来看一看怎样用这些方法对桌上一付乱序的牌进行排序.牌既要按花色排序(依次为梅花.方块.红桃与黑心),还要按点数排序(从2到a).
插入排序的过程为:从一堆牌的上面开始拿牌,每次拿一张牌,按排序原则把牌放到手中正确的位置.桌上的牌拿完后,手中的牌也就排好序了. 交换排序的过程为: (1)先拿两张牌放到手中.如果左边的牌要排在右边的牌的后面,就交换这两张牌的位置. (2)然后拿下一张牌,并比较最右边两张牌,如果有必要就交换这两张牌的位置. (3)重复第(2)步,直到把所有的牌都拿到手中. (4)如果不再需要交换手中任何两张牌的位置,就说明牌已经排好序了;否则,把手中的牌放到桌上,重复(1)至(4)步,直到手中的牌排好序. 选择排序的过程为:在桌上的牌中找出最小的一张牌,拿在手中;重复这种操作,直到把所有牌都拿在手中. 归并排序的过程为:把桌上的牌分为52堆,每堆为一张牌.因为每堆牌都是有序的(记住,此时每堆中只有一张牌),所以如果把相邻的两堆牌合并为一堆,并对每堆牌进行排序,就可以得到26堆已排好序的牌,此时每一堆中有两张牌.重复这种合并操作,就可以依次得到13堆牌(每一堆中有4张牌),7堆牌(有6堆是8张牌,还有一堆是4张牌),最后将得到52张的一堆牌. 分布排序(也被称作radix sort,即基数排序)的过程为:先将牌按点数分成13堆,然后将这13堆牌按点数顺序叠在一起;再将牌按花色分成4堆,然后将这4堆牌按花色顺序叠在一起,牌就排好序了. 在选用排序算法时,你还需要了解以下几个术语: (1)自然的(natural) 如果某种排序算法对有序的数据排序速度较快(工作量变小),对无序的数据排序速度却较慢(工作变量大),我们就称这种排序算法是自然的.如果数据已接近有序,就需要考虑选用自然的排序算法. (2)稳定的(stable) 如果某种排序算法能保持它认为相等的数据的前后顺序,我们就称这种排序算法是稳定的. 例如,现有以下名单: mary jones mary smith tom jones susie queue 如果用稳定的排序算法按姓对上述名单进行排序,那么在排好序后"mary jones”与"tom jones”将保持原来的jr顺序,因为它们的姓是相同的. 稳定的排序算法可按主.次关键字对数据进行排序,例如按姓与名排序(换句话说,主要按姓排序,但对姓相同的数据还要按名排序).在具体实现时,就是先按次关键字排序,再按主关键字排序. (3)内部排序(internal sort)与外部排序(external sort) 待排数据全部在内存中的排序方法被称为内部排序,待排数据在磁盘.磁带与其它外存中的排序方法被称为外部排序.查 找
与排序算法一样,查找(searching)算法也是计算机科学中研究得最多的问题之一.查找算法与排序算法是有联系的,因为许多查找算法依赖于要查找的数据集的有序程度.基本的查找算法有以下4种:
·顺序查找(sequential searching). ·比较查找(comparison searching) ·基数查找(radix searching) ·哈希查找(hashing) 下面仍然以一付乱序的牌为例来描述这些算法的工作过程. 顺序查找的过程为:从第一张开始查看每一张牌,直到找到要找的牌. 比较查找(也被称作binarysearching,即折半查找)要求牌已经排好序,其过程为:任意抽一张牌,如果这张牌正是要找的牌,则查找过程结束.如果抽出的这张牌比要找的牌大,则在它前面的牌中重复查找操作;反之,则在它后面的牌中重复查找操作,直到找到要找的牌. 基数查找的过程为:先将牌按点数分成13堆,或者按花色分成4堆.然后找出与要找的牌的点数或花色相同的那一堆牌,再在这堆牌中用任意一种查找算法找到要找的牌. 哈希查找的过程为: (1)在桌面上留出可以放若干堆牌的空间,并构造一个函数,使其能根据点数与花色将牌映射到特定的堆中(这个函数被称为hashfunction,即哈希函数). (2)根据哈希函数将牌分成若干堆. (3)根据哈希函数找到要找的牌所在的堆,然后在这一堆牌中找到要找的牌. 例如,可以构造这样一个哈希函数: pile=rank+suit 其中,rank是表示牌的点数的一个数值;suit是表示牌的花色的一个数值;pile表示堆值,它将决定一张牌归入到哪一堆中.如果用1,2,……,13分别表示a,2,……．k,用0,1,2与3分别表示梅花.方块.红桃与黑桃,则pile的值将为1,2,……,16,这样就可以把一付牌分成16堆. 哈希查找虽然看上去有些离谱,但它确实是一种非常实用的查找算法.各种各样的程序,从压缩程序(如stacker)到磁盘高速缓存程序(如smartdrive),几乎都通过这种方法来提高查找速度, 排序或查找的性能 有关排序与查找的一个主要问题就是速度.... 下一页