C语言程序设计中选择结构排序算法研究

张 晨

(安徽建筑大学 城市建设学院，安徽 合肥 238076)

当今是信息时代，计算机处理数据信息的范围越来越广，需要比较的东西也越来越多，这与C语言程序有关，结构化程序设计在 C语言程序设计中尤为重要[1]。其程序结构包括序列结构、选择结构和循环结构，在 C语言编程教学中，排序算法应用广泛、使用频繁[2]，因此，对排序算法的研究一直是计算机领域的一个热点问题。以往大都使用快速排序、堆排序和归并排序方法，这三种方法涉及的问题复杂，受到选择结构排序比较次数影响，导致排序效果较差。为了优化堆排序和编程优化的次数，研究C语言程序设计中选择结构排序算法，提高其排序结果的稳定性十分必要。

1 选择结构排序算法原理

C语言源程序可由一个或多个源文件组成，每个源文件可由一个或多个函数组成；不管一个源程序有多少个文件，它都有一个主函数；可以在源程序中包含预处理命令，通常将其置于源文件或源程序之前；每条语句都必须以分号结尾[3-4]。但是，对于预处理命令，不能在函数标题和括号“}”的后面加上分号；用于表示时间间隔的标识符和关键字之间至少要添加一个空格。如果有明显的空白字符，也可以不显示空白[5-6]。在编程时遵循的规则提高了算法的质量，使得设计和阅读更方便。对箭头的滥用必须加以限制，也就是说，不能让它乱成一团，而是要有条不紊[7]。但该算法必须包含某些分支和循环，并且不可能全部由无序组成，需要使用选择结构来解决此问题[8]。

选择结构包括判断方框的流程图，根据给定的条件P是否正确，选择了执行A和B，不管用什么方法，都会选择是在结构之后执行，还是在 B和A两个判断方框中之前执行，选择结构流程如图1所示。

图1 选择结构流程图

由图1可知，选择结构排序是指按照关键字重新排列一系列数据或元素，使其按顺序(增加或减少)排列[9-10]。资料处理时，假设档案中的项目(或记录)为：R1，R2，R3，…，Rn

关键字分别是：K1，K2，K3，…，Kn，

那么排序结果就是将这n个元素按照关键字的条件要求(Ki≤Ki2≤Ki3≤…≤Kin或Ki≥Ki2≥Ki3≥…≥Kin)重新排列为：

Ri1，Ri2，Ri3，…，Rin

选择结构的选取采用了交换排序法，换序的基本思想是通过比较成对数组来确定一个顺序。如有不符合之处，将兑换[11]。同样，保持原来的次序，直到所有的关键字都达到指定的次序。根据“轻的高，重的低”的原则，对排序后的记录数组进行重复扫描，直到轻泡上，重泡下[12]。为此，提出了一种改进的冒泡排序算法，它的基本思想是选择当前无序数组中的任意元素作为基值temp，它用来将数组划分为两个较小的无序数组，即左边的记录小于基值temp，右边的记录大于基值temp，最后一个排序位置为基值temp。用这种方法重复这一过程，直到所有的记录都完成为止[13]。

2 C语言程序设计中的选择结构排序算法设计

C语言是一种结构化语言，可以在硬件上实现编程操作，可以用来开发系统软件，也可以用来开发应用软件。此外，由于C语言的高效率和可移植性，它被广泛地移植到各种类型的计算机上，从而形成了不同版本的C语言。Select排序是一个重要的算法，它建立在选择原则的基础上，选择最小(或最大)的元素，用第一个元素交换它，然后用最小(或最大)元素中剩下的元素交换它，直到所有数据元素都排好。因为每个选择都是数据的最小(或最大)值，所以称之为选择排序。

C语言表达式由操作符和操作数据组成，每个操作符具有优先权和绑定规则。具有更高优先级的操作符会将操作数组合起来，而不必用括号表示。如果两个运算子有相同的优先级，则根据合并规则，使运算子与运算子一致。

假设有5组数据，分别是85、61、72、94、50存储到C语言数组Bs中，对这5组数据进行升序排序设计。要对C语言数据进行升序设计时，需每次选择最小的数据放在最前方。

2.1 第1趟排序过程

第1趟排序过程如表1所示。

表1 第1趟排序过程

由表1可知，5组数组下标的元素分别与Bs{m}相比存在两种可能性：①如果数组下标的元素比数组大，则需更改最小下标值；②如果数组下标的元素比数组小，则最小下标值不变。

如果使用变量J表示元素下标，则可以将比较过程表示为：if(Bs{j}

设m=1

比较：for(j=1；j<=5；j++)

if(Bs{j}

交换：将数组Bs{1}和Bs{m}交换，数据50为最小元素，与数据85交换，放置在第一位。

第1趟排序过程确定了最小数据，也是第一个位置，还要继续在剩余位置中进行选择交换。

2.2 第2趟排序过程

第2趟排序过程如表2所示。

表2 第2趟排序过程

由表2可知，第2趟排序过程一共对比了3次，4组数组中下标元素分别跟Bs{m}对比，确定第2趟排序过程中的最小值。

设m=2

比较：for(j=2；j<=5；j++)

if(Bs{j}

交换：将数组Bs{2}和Bs{m}交换。

第2趟排序过程确定了第二个数据，也是第二个位置，还要继续在剩余位置中进行选择交换。

2.3 第3趟排序过程

以此类推，第3趟排序过程对比了两次，数组中下标元素分别跟Bs{m}对比，确定第三个数据。

设m=3

比较：for(j=3；j<=5；j++)

if(Bs{j}

交换：将数组Bs{3}和Bs{m}交换。

2.4 第4趟排序过程

第4趟只对比了1次，将数组下表中的元素分别与Bs{m}对比，确定第四个最小数据，同时也确定了第五个数据，排序结束。

设m=4

比较：for(j=4；j<=5；j++)

if(Bs{j}

交换：将数组Bs{4}和Bs{m}交换。

通过上述排序过程可看出，5组数组中共排序4趟，第1趟比较4次，第2趟比较3次，第3趟比较2次，第4趟比较1次。每趟排序交换后的数据排序结果如图2所示。

图2 每趟排序交换后的数据排序结果

通过图2所示的排序结果，即可完成C语言升序排序设计。

3 实验分析

为了验证C语言程序设计中选择结构排序算法研究的合理性，进行了实验验证分析。

C语言程序执行过程中，由用户选择菜单，触动计算器开始工作。假设C语言计算器程序中存在5组数据，分别将92、68、60、88、70存储到C语言数组Fs中，分别使用快速排序、堆排序、归并排序方法和选择结构排序方法，对上述5组数据排序，对比上述5组数据的排序时间，对比结果如表3所示。

表3 5组数据排序时间对比分析 s

根据表3可知，采用快速排序方法对上述5组数据进行排序的时间在12.9-15.8 s之间，采用堆排序方法对5组数据进行排序的时间在19.2-28.7 s之间，采用归并排序方法对5组数据进行排序的时间在31.5-40.8 s之间，采用选择结构排序方法对5组数据进行排序的时间在3.1-5.0 s之间，采用选择结构排序方法对5组数据进行排序的时间比其他三种方法的排序时间短，说明使用选择结构排序方法，排序效率较高。

4 结论

针对C语言程序设计中的选择结构排序算法进行分析，指出判定排序结果好坏的标准是待排序记录的比较时间较少，占用的空间较小。没有任何一种排序方法能对文件的初始状态进行最佳排序，所以在处理实际问题时应综合考虑，选择更适合的排序方法，并对性能分析结果进行比较。虽然使用该方法的效果良好，但实验条件受到限制，因此，在后期需根据多种方法来实现预期目标。