·138-
浅谈冒泡排序与选择排序
高爱梅
(内蒙古电子信息职业技术学院，内蒙吉呼和浩特010070）
信息技术
摘要：排序是C语言中一类穷举算法问题，主要对冒泡排序和选择排序的排序思想、排序过程及代码实现进行介绍，最后对其分析并找出改进每一种排序方法的思路，让读者今后更好的理解、适用这两种排序方法
关键词：冒泡排序；选择排序；记录值
排序是任何一门程序设计课程中都涉及的内容，是实现组织和处理数据的一种基本运算形式,它的作用是将一组给定的数据(整型、实型、字符型)按要求排列成一个有序序列的过程。在C语言中排序方法很多，这里只介绍简单冒泡排序和直接选择排序，两种排序的基本思想和具体实现过程各不相同。让读者更容易理解、掌握这两种排序方法，现以升序为例将每一种方法的排序思想、C程序代码和实现过程等进行详细说明。
1冒泡排序
1.1排序简介。在计算机排序范围中属于一种简单的排序算法，排序过程中较小的数放到前面较大的数放到后面，类似气泡不断往水面上升，称为骨泡排序。
1.2排序代码
#include
#define N 5 main)
[int a[Njijl
printf("Input 5 numbersc(n");
for(i=0;i<5;i++)[P%.us n.ud
for(i=0;i for(j=0ja
[=a aa[+1] a[+1t:] printf("The sorted numbers'n"):
for(i=0;i<=N;i++) printf("%d "ai
1.3过程分析。假设程序运行时通过键盘输人38，49，65，76，13这五个数，按照由小到大进行排序(方括号内的属于无序区)。
具体排序过程如下：a.将整个记录序列划分为无序区和有序区，刚开始无序区包含所有待排序的记录。h在无序区从前到后依次比较相邻记录，若反向则交换记录值，最终实现较小记录值往前移，较大记录值往后移。e不断重复进行步媒b，直到无序区没有反序记录为止。
初始序列[38,49,65,76,13]
第一轮序结果i=0)：[38，49，65，13]，76 第二轮拌序结果（1=1)：[38，49，13].65.76 第三轮拌序结果(i=2：[38，13]，
49.65.76
第四轮排序结果（i=3：[13].
38.49.65.76
图1冒泡排序过程示例
2选择排序 2.1排序简介
该方法也是一种简单直观的排序方法，每一次从待排序的数列中找出最小或最大的数放到有序序列的起始位置，直到全部排完
2.2程序代码
#inelude
#define N 5 main)
[int a[N]ijk,x;
printi('Input 5 numbersc(n") for(i=0;i<5;i++)
scanf(*%d",&ai):
printl"n" forfi=0ki<4;i++)
for(j=i+1:j<=4:j++) ilalikakp k=j: it=k)
(x=a[ii=a[kk=x:) 1
printf("The sorted numbers:(n");
for(i=0,i<5,i++):r P%ud
2.3过程分析。具体排序过程如下：a将整个记录序列划分为有序区和无序区，刚开始有序区为空，无序区含有待排序的所有记录。h在无序区查找值最小的记录，将最小值与无序区第一个记录交换，使有序区增加一个记录，无序区减少一个记录。e不断重复进行步案b，直到无序区只剩下一个记录值为止。
初始序列:[38,49,65,76,13]
第—轮排序结果（1=0)：13，［49，65.76.38] 第二轮排序结果（i=1)：13，38，[65,76,49] 第三轮排序结果（i=2：13，38，49,[76,65] 第四轮排序结果（1=3：13，38，49.65，[76]
图2选择排序过程示例
3比较总结
判断一种算法的优略，主要从空间复杂度和时间复杂度两个方面考虑。下面对冒泡排序和选择排序分别进行分析、说明：
3.1对于膏泡排序而言，空间方面只用了一个辅助单元，排序稳定，时间方面N个记录需要N-1轮排序，对于个记录的无序序列进行一轮排序需要j-1次记录值比较，总比较次数为0(n2)各个记录需要交换的次数：最理想的情况该序列已有序不需要交换；最差的情况每次比较后都得进行交换三次.总交换次数为：0n2)。经分析，要提高简单冒泡排序效率我们应做如下改进：当进行每一轮比较时，对交换的数据做一个标记，即标志值为1发生交换否则未交换。只要标志值为0.就会停止循环扫描，减少扫描的次数，这样有效的降低时间复杂度。带标志冒泡排序对于大批量数据排序很有效。
3.2对于选择排序而言，空间方面也是用了一个辅助单元，排序不稳定，时间方面N个记录同样需要N-1轮排序，比较次数与记录初始序列无关，序列初态为正序时，移动次数为0；最差状况每轮排序都进行交换，总的移动次数为3(n-1)，交换记录只执行一次，直接选择排序最终的平均时间复杂度仍为T(n)=0(n2).经分析，要提高直接选择排序的效率我们应做如下改进：在传统选择排序的基础上，我们可以在一轮比较完成后能同时找到当前最大值和最小值，分别放到对应的第一个位置和最后一个位置，这样比较轮数就会减少一半，达到降低时间复杂度
在C语言中排序方法很多，但是每一种排序算法既有优点又有缺点。本文对胃泡法和选择法的排序思想在时间效率方面改进是合理、有效的。我们对给定数据记录进行排序时应从多角度考患并试着采取多种方法实现
参考文献
[1]王红梅、胡明.算法设计与分析(第2版)[M]北京；清华大学出航社， 2013.
[2|谭浩强C语言程序设计(第3版)M)北京：清华大学出版社,2009.