《C语言排序与查找》由会员分享，可在线阅读，更多相关《C语言排序与查找（14页珍藏版）》请在金锄头文库上搜索。
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 张的 一堆牌。分布排序分布排序(也被称作也被称作 radix sort，即基数排序，即基数排序)的过程为：的过程为： 先将牌按点数分成 13 堆，然后将这 13 堆牌按点数顺序叠在一起；再将牌按花色分成 4 堆，然后将这 4 堆牌按花色顺序叠在一起，牌就排好序了。在选用排序算法时，你还需要了解以下几个术语： 1、自然的、
4、自然的(natural) 如果某种排序算法对有序的数据排序速度较快(工作量变小)，对无序的数据排序速度却较慢(工作变量大)，我们就称这种排序算法是自然的。如果数据已接近有序，就需要考 虑选用自然的排序算法。2、稳定的、稳定的(stable) 如果某种排序算法能保持它认为相等的数据的前后顺序，我们就称这种排序算法是稳 定的。 例如，现有以下名单：Mary JonesMary SmithTom JonesSusie Queue如果用稳定的排序算法按姓对上述名单进行排序，那么在排好序后“Mary Jones”和 “Tom Jones”将保持原来的 Jr 顺序，因为它们的姓是相同的。稳定的排序算法可按
5、主、次关键字对数据进行排序，例如按姓和名排序(换句话说，主 要按姓排序，但对姓相同的数据还要按名排序)。在具体实现时，就是先按次关键字排序， 再按主关键字排序。3、内部排序、内部排序(internal sort)和外部排序和外部排序(external sort) 待排数据全部在内存中的排序方法被称为内部排序，待排数据在磁盘、磁带和其它外 存中的排序方法被称为外部排序。4 种基本的种基本的 C 语言查找算法语言查找算法和排序算法一样，查找(searching)算法也是计算机科学中研究得最多的问题之一。查 找算法和排序算法是有联系的，因为许多查找算法依赖于要查找的数据集的有序程度。基本的查找算法有
6、以下 4 种： 1.顺序查找(sequential searching) 2.比较查找(comparison searching) 3.基数查找(radix searching) 4.哈希查找(hashing)下面仍然以一付乱序的牌为例来描述这些算法的工作过程。 顺序查找的过程为：顺序查找的过程为： 从第一张开始查看每一张牌，直到找到要找的牌。比较查找比较查找(也被称作也被称作 binarysearching，即折半查找，即折半查找)要求牌已经排好序，其过程为：要求牌已经排好序，其过程为： 任意抽一张牌，如果这张牌正是要找的牌，则查找过程结束。如果抽出的这张牌比要 找的牌大，则在它前面的牌中重
7、复查找操作；反之，则在它后面的牌中重复查找操作，直 到找到要找的牌。基数查找的过程为：基数查找的过程为： 先将牌按点数分成 13 堆，或者按花色分成 4 堆。然后找出与要找的牌的点数或花色 相同的那一堆牌，再在这堆牌中用任意一种查找算法找到要找的牌。哈希查找的过程为：哈希查找的过程为：(1)在桌面上留出可以放若干堆牌的空间，并构造一个函数，使其能根据点数和花色将 牌映射到特定的堆中(这个函数被称为 hashfunction，即哈希函数)。(2)根据哈希函数将牌分成若干堆。 (3)根据哈希函数找到要找的牌所在的堆，然后在这一堆牌中找到要找的牌。 例如，可以构造这样一个哈希函数： pile=ran
8、k+suit 其中，rank 是表示牌的点数的一个数值；suit 是表示牌的花色的一个数值；pile 表示堆值， 它将决定一张牌归入到哪一堆中。如果用 1，2，13 分别表示 A，2，K，用 0，1，2 和 3 分别表示梅花、方块、红桃和黑桃，则 pile 的值将为 1，2，16，这样 就可以把一付牌分成 16 堆。哈希查找虽然看上去有些离谱，但它确实是一种非常实用的查找算法。各种各样的程序， 从压缩程序(如 Stacker)到磁盘高速缓存程序(如 SmartDrive)，几乎都通过这种方法来提高 查找速度。C 语言排序或查找的性能分析语言排序或查找的性能分析有关排序和查找的一个主要问题就是速
9、度。这个问题经常被人们忽视，因为与程序的 其余部分相比，排序或查找所花费的时间几乎可以被忽略。然而，对大多数排序或查找应 用来说，你不必一开始就花很多精力去编制一段算法程序，而应该先在现成的算法中选用 一种最简单的(见 31 和 34)，当你发现所用的算法使程序运行很慢时，再换用一种更 好的算法(请参见下文中的介绍)。下面介绍一种判断排序或查找算法的速度的方法。下面介绍一种判断排序或查找算法的速度的方法。 首先，引入一个算法的复杂度的概念，它指的是在各种情况(最好的、最差的和平均的)下 排序或查找需要完成的操作次数，通过它可以比较不同算法的性能。算法的复杂度与排序或查找所针对的数据集的数据量有
10、关，因此，引入一个基于数据集数 据量的表达式来表示算法的复杂度。最快的算法的复杂度最快的算法的复杂度 O(1)，它表示算法的操作次数与数据量无关。，它表示算法的操作次数与数据量无关。 复杂度 O(N)(N 表示数据集的数据量)表示算法的操作次数与数据量直接相关。复杂度 O(logN)介于上述两者之间，它表示算法的操作次数与数据量的对数有关。复杂度为 O(NlogN)(N 乘以 logN)的算法比复杂度为 O(N)的算法要慢，而复杂度为 O(N2)的算法更慢。注意：如果两种算法的复杂度都是 O(logN)，那么 logN 的基数较大的算法的速度要快些， 在本章的例子中，logN 的基数均为 10
11、。表 31 本章所有算法的复杂度-算 法 最好情况 平均情况 最坏情况-快速排序 O(NlogN) O(NlogN) O(N2)归并排序 O(N) O(NlogN) O(NlogN)基数排序 O(N) O(N) O(N) 线性查找 O(N)折半查找 O(NlogN)哈希查找 O(N/M)*健树查找 O(1)*- * M 是哈希表项的数目 * 实际上相当于有 232个哈希表项的哈希查找表 3. 1 列出了本章所有算法的复杂度。对于排序算法，表中给出了最好的、平均的和 最差的情况下的复杂度，平均情况是指数据随机排列的情况；排序算法的复杂度视数据的 初始排列情况而定，它一般介于最好的和最差的两种情况
12、之间。对于查找算法，表中只给 出了平均情况下的复杂度，在最好的情况(即要找的数据恰好在第一次查找的位置)下，查 找算法的复杂度显然是 O(1)；在最坏的情况(即要找的数据不在数据集中)下，查找算法的复杂度通常与平均情况下的复杂度相同。 需要注意的是，算法的复杂度只表示当 N 值变大时算法的速度变慢的程度，它并不表 示算法应用于给定大小的数据集时的实际速度。算法的实际速度与多种因素有关，包括数 据集的数据类型以及所用的编程语言、编译程序和计算机等。换句话说，与复杂度高的算 法相比，复杂度低的算法并不具备绝对的优越性。实际上，算法的复杂度的真正意义在于， 当 N 值大于某一数值后，复杂度低的算法就
13、会明显比复杂度高的算法快。为了说明算法的复杂度和算法的实际执行时间之间的关系，表 32 列出了本章所有 例子程序的执行时间。本章所有例子程序均在一台以 Linux 为操作系统的 90MHz 奔腾计算 机上由 GNU C 编译程序编译，在其它操作系统中，这些例子程序的执行时间与表 32 所 列的时间是成比例的。表 3. 2 本章所有例子程序的执行时间-例子程序 算 法 2000 4000 6000 8000 10000-例 31 qsort() 002 005 007 011 0，13例 32a 快速排序 002 007 013 018 020例 32b 归并排序 003 008 014 018 026例 32c 基数排序 007 015 023 030 039例 34 bsearch() 0. 37 039 039 040 041例 35 折半查找 032 034 034 036 036例 36 线性查找 967 2068 2871 3631 45. 51例 37 键树查找 027 028 029 029 030例 38 哈希查找 025 026 028 029 028-注意： (1)表中所列的时间以秒为单位。 (2)表中所列的时间经过统一处理，只包括排序或查找所
