c语言排序与查找

《c语言排序与查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言五种基本排序算法1.插入排序(insertionsort．)2.交换排序(exchangesOrt)3.选择排序(selectionsort)4.归并排序(mergesort)5.分布排序(distributionsort)为了形象地解释每种排序算法是怎样工作的，让我们来看一看怎样用这些方法对桌上一付乱序的牌进行排序。牌既要按花色排序(依次为梅花、方块、红桃和黑心)，还要按点数排序(从2到A)。插入排序的过程为：从一堆牌的上面开始拿牌，每次拿一张牌，按排序原则把牌放到手中正确的位置。桌上的牌拿完后，手中的牌也就排好序了。交换排序的过程为：   (

2、1)先拿两张牌放到手中。如果左边的牌要排在右边的牌的后面，就交换这两张牌的位置。   (2)然后拿下一张牌，并比较最右边两张牌，如果有必要就交换这两张牌的位置。   (3)重复第(2)步，直到把所有的牌都拿到手中。   (4)如果不再需要交换手中任何两张牌的位置，就说明牌已经排好序了；否则，把手中的牌放到桌上，重复(1)至(4)步，直到手中的牌排好序。选择排序的过程为：在桌上的牌中找出最小的一张牌，拿在手中；重复这种操作，直到把所有牌都拿在手中。归并排序的过程为：把桌上的牌分为52堆，每堆为一张牌。因为每堆牌都是有序的(记住，此时每堆中只有一张牌)，所

3、以如果把相邻的两堆牌合并为一堆，并对每堆牌进行排序，就可以得到26堆已排好序的牌，此时每一堆中有两张牌。重复这种合并操作，就可以依次得到13堆牌(每一堆中有4张牌)，7堆牌(有6堆是8张牌，还有一堆是4张牌)，最后将得到52张的一堆牌。分布排序(也被称作radixsort，即基数排序)的过程为：先将牌按点数分成13堆，然后将这13堆牌按点数顺序叠在一起；再将牌按花色分成4堆，然后将这4堆牌按花色顺序叠在一起，牌就排好序了。在选用排序算法时，你还需要了解以下几个术语：1、自然的(natural)如果某种排序算法对有序的数据排序速度较快(工作量变小)，对无

4、序的数据排序速度却较慢(工作变量大)，我们就称这种排序算法是自然的。如果数据已接近有序，就需要考虑选用自然的排序算法。2、稳定的(stable)如果某种排序算法能保持它认为相等的数据的前后顺序，我们就称这种排序算法是稳定的。    例如，现有以下名单：   MaryJones   MarySmith   TomJones   SusieQueue如果用稳定的排序算法按姓对上述名单进行排序，那么在排好序后"MaryJones”和"TomJones”将保持原来的Jr顺序，因为它们的姓是相同的。稳定的排序算法可按主、次关键字对数据进行排序，例如按姓和名排序(

5、换句话说，主要按姓排序，但对姓相同的数据还要按名排序)。在具体实现时，就是先按次关键字排序，再按主关键字排序。3、内部排序(internalsort)和外部排序(externalsort)待排数据全部在内存中的排序方法被称为内部排序，待排数据在磁盘、磁带和其它外存中的排序方法被称为外部排序。4种基本的C语言查找算法和排序算法一样，查找(searching)算法也是计算机科学中研究得最多的问题之一。查找算法和排序算法是有联系的，因为许多查找算法依赖于要查找的数据集的有序程度。基本的查找算法有以下4种：1.顺序查找(sequentialsearching)

6、2.比较查找(comparisonsearching)3.基数查找(radixsearching)4.哈希查找(hashing)下面仍然以一付乱序的牌为例来描述这些算法的工作过程。顺序查找的过程为：从第一张开始查看每一张牌，直到找到要找的牌。比较查找(也被称作binarysearching，即折半查找)要求牌已经排好序，其过程为：任意抽一张牌，如果这张牌正是要找的牌，则查找过程结束。如果抽出的这张牌比要找的牌大，则在它前面的牌中重复查找操作；反之，则在它后面的牌中重复查找操作，直到找到要找的牌。基数查找的过程为：先将牌按点数分成13堆，或者按花色分成4

7、堆。然后找出与要找的牌的点数或花色相同的那一堆牌，再在这堆牌中用任意一种查找算法找到要找的牌。哈希查找的过程为：   (1)在桌面上留出可以放若干堆牌的空间，并构造一个函数，使其能根据点数和花色将牌映射到特定的堆中(这个函数被称为hashfunction，即哈希函数)。   (2)根据哈希函数将牌分成若干堆。      (3)根据哈希函数找到要找的牌所在的堆，然后在这一堆牌中找到要找的牌。   例如，可以构造这样一个哈希函数：    pile=rank+suit其中，rank是表示牌的点数的一个数值；suit是表示牌的花色的一个数值；pile表示堆值，

8、它将决定一张牌归入到哪一堆中。如果用1，2，……，13分别表示A，2，……．K，用0，1，2和