C语言编程常见问题解答之排序与查找

文章作者 100test 发表时间 2007:03:10 17:38:12
来源 100Test.Com百考试题网

第3章 排序与查找

在计算机科学中，排序(sorting)是研究得最多的问题之一，许多书籍都深入讨论了这个问题。本章仅仅是一个介绍，重点放在C语言的实际应用上。
排 序
程序员可以使用的基本排序算法有5种：
·插入排序(insertionsort．)
·交换排序(exchangesOrt)
·选择排序(0selectionsort)
·归并排序(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，即折半查找)要求牌已经排好序，其过程为：任意抽一张牌，如果这张牌正是要找的牌，则查找过程结束。如果抽出的这张牌比要找的牌大，则在它前面的牌中重复查找操作；反之，则在它后面的牌中重复查找操作，直到找到要找的牌。