典型算法应用

《典型算法应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第18章典型算法应用算法是对特定问题求解步骤的描述。对于同一个问题，可能用不同算法来求解，程序员可根据算法的可读性、效率等进行取舍。针对不同的数据保存方式，也会有不同的算法。本章将重点介绍C语言程序设计中的常用算法，也会穿插着简单介绍常用数据和数据结构的内容。18.1排序排序是将一组数据按递增或递减的顺序排列。排序算法是一种基本的且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。排序算法很多，本节将介绍几种常用的排序算法，在本节的算法中，都是按递增排序，递减排序的方法与之类似。18.1.1排序概述在前面的内容中曾多次使用自

2、然排序法，即通过一个双重循环逐个将有序的数据向前推，从而使数据排列成一个有序组合。在双重循环中都是对数组中的数据进行排序。对数组中的元素进行排序比较方便，因为数组中的每个元素在任何时候都可以方便地与其他元素进行比较和交换。下面的排序算法都是针对数组元素排序。对数组排序的方法一般有三种：¾交换排序；¾选择排序；¾插入排序。这三种方法将在后面的排序算法中分别介绍。排序算法有很多种，每种算法都有其优缺点，可适应不同的场合。可从以下几方面判断一个排序算法的优劣：¾算法描述的复杂程度；¾一般情况下该算法的速度；¾极端情况下该算法的速度。C语言开发手册（典藏版）可以

3、看出，速度是决定排序算法最主要的因素。但是，在计算机硬件速度飞速发展的今天，算法的可读性显得更加重要。例如，本书前面用到的自然排序算法，使用交换排序的方法，每次将余下数中的最大（最小）数找出来。这种算法很容易理解，但执行效率低，仍被广泛使用。因为，虽然其执行效率低，但在高速CPU、不是很大的数据量的情况下，用户感觉不出该算法和其他算法在效率上的差距。18.1.2冒泡排序法冒泡排序法使用的方法是交换排序。其基本思路是：对数组中尚未排序的各元素，依次比较相邻的两个元素的大小，若前面的元素大于后面的元素，就交换这两元素，经过第一轮比较排序后便可把最小的元素排好

4、。然后再用同样的方法把剩下的元素逐个进行比较，就可排好数组各元素的顺序。下面举例说明冒泡排序法在数组排序中的应用，程序示例如下：【程序18-1】#include//头文件#include#include#defineN10//数组大小voidmaopao(int*a,intn);intmain(){intarr[N],i;srand(time(NULL));for(i=0;i

5、ii;j--){if(a[j-1]>a[j]){t=a[j-1];a[j-1]=

6、a[j];a[j]=t;}}}}在该程序中，定义一个符号常量，用于决定需要排序数组的大小。然后，分别为排序算法函数的原型声明和调用。程序中使用时间函数time()生成一个随机种子，控制rand()函数生成的随机数，并将生成数据保存到数组元素中。然后，将该数组输出。接着，调用冒泡排序法对该数组进行排序，并输出排序后的结果。编译执行这段程序，得到如下结果，如图18-1所示。为了让读者看清冒泡排序函数的执行过程，下面列出对5个整型数据排序时的过程，如图18-2所示。排序过程如下：初始数据：116103105120114一次排序：103116105114120二

7、次排序：103105116114120三次排序：103105114116120四次排序：103105114116120图18-1执行结果图18-2冒泡排序过程第1次排序从数组的尾部开始向前比较，将数据114向上移了一位，将103向前移了一位。第2次排序将105向前移了一位。第3次排序将114向前移了一位。第4次排序时，因各数据已经按顺序排列好，所以没有数据交换。从上面的执行过程可以看出，使用冒泡排序法对n个数据进行排序，共需要进行n-1次的比较。如果本来就是有顺序的数据，也需要进行n-1次比较。冒泡排序法的算法很简单，效率也较差。读者可试着对上面的算法进

8、行修改，提高该算法的效率。18.1.3选择排序法选择排序法也是经常使用的排序方法