基于C语言的几种排序方法比较

【摘要】文章对c语言中的冒泡排序法、选择排序法、插入排序法进行比较讨论，以试图找出最佳排序方法。

【关键词】c语言;排序方法;比较

引言

排序是计算机程序设计中的一种重要操作，其作用是将一个数据元素（或记录）的任意序列重新排列成一个（按关键字）有序的序列[1]。按照排序记录数量分为内部排序及外部排序两类。若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序。反之，若参与排序的记录数量很大，使内存不能一次容纳全部的记录，所以排序过程中需要对外存进行访问，则称此类排序为外部排序。 换句话说，内部排序仅适合待排序记录数量相对较少的序列。内部排序方法分类较多，按照排序过程依据的原则不同分类，大致分为五类：插入排序、交换排序、选择排序、归并排序和基数排序等。这里介绍的冒（起）泡排序大致属于交换排序中的一种排序方法，下面将就c语言中冒泡排序法、选择排序法、插入排序法进行比较讨论，以试图找出最佳排序方法.

1.冒泡排序法（起泡法）

1.1 冒泡排序算法分析

冒泡法算法分析：如果有n个待排序数据，需要进行n-1趟比较。在第1趟比较中，要进行n-1次相邻元素的两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过一趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降序。

1.2 实现冒泡排序算法c语言源程序清单

#include <stdio.h>

#include <malloc.h>

main（ ）

{ int *a ， i ，j ， t， n ;

printf （ “请输入需排序元素个数 ： n=” ）;

scanf（" %d"，&n）; a=（int *）malloc（sizeof（int）*n）;

printf （ “请输入每个数组元素 ：” ）;

for （i=1;i<=n;i=i+1） scanf（“ %d”，&a[i]）;

for （i=1;i<=n-1;i++）

for （j=1;j<=n-i;j++）

if （a[j]>a[j+1]） {t=a[j];a[j]=a[j+1];a[j+1]=t;}

printf（ “排序后的数组为 ： “）;

for （i=1;i<=n;i=i+1） printf （ "%d "，a[i]）; }

1.3 冒泡排序算法特点

相邻元素两两比较，每趟将最值沉底即可确定一个数在结果的位置，确定元素位置的顺序是从后往前，其余元素可能作相对位置的调整。可以进行升序或降序排序。 该排序方法的优点是比较原则简单，排序序列相对稳定;缺点是速度慢，每次只能比较移动相邻两个数据，每一趟只能减少一个数据，参与排序的记录数量相对较少。

2.选择排序法

2.1 选择排序算法分析

选择排序法的算法分析：每趟选出一个最值和无序序列的第一个数交换，n个数共选n-1趟。第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值下标不为初设值，则将最值元素和下标为i的元素交换。

2.2 实现选择排序算法c语言源程序清单

以降序为例：

#include <stdio.h>

#include <malloc.h>

main（ ）

{ int *a ， i ，j ， t，k， n ;

printf （ “请输入需排序元素个数 ： n=” ）;

scanf（" %d"，&n）; a=（int *）malloc（sizeof（int）*n）;

printf （ “请输入每个数组元素 ：” ）;

for （i=0;i<n;i=i+1） scanf（" %d"，&a[i]）;

for（i=0;i<n-1;i++）

{ k=i;

for（j=i+1;j<n;j++）

if（a[k]<a[j]）

k=j;

if（k！=i）

{t=a[k];a[k]=a[i];a[i]=t; } }

printf（ “排序后的数组为 ：＼n”）;

for （i=0;i<n;i=i+1） printf（ " %d"，a[i]）; }

2.3 选择排序算法特点

选择排序法的算法特点：每趟是选出一个最值，确定它在结果序列中的位置，确定元素的位置是从前往后，而每趟最多进行一次交换，此方法移动元素的次数比较少，其余元素的相对位置不变。

3.插入排序法

3.1 插入排序算法分析

插入排序的算法分析：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。

3.2 实现插入排序算法c语言源程序清单

以降序为例：

#include <stdio.h>

#include <malloc.h>

main（ ）

{ int *a ， i ，j ， t， n ;

printf （ “请输入需排序元素个数 ： n=” ）; scanf （“ %d”，&n）;

a=（int *）malloc（sizeof（int）*n）;

printf （ “请输入每个数组元素 ：” ）;

for （i=0;i<n;i=i+1） scanf（" %d"，&a[i]）;

for（i=1;i<n;i++）

{ t=a[i];

for（ j=i-1;j>=0 && t>a[j];j-- ）

a[j+1]=a[j];

a[j+1]=t; }

printf（ “排序后的数组为 ： “）;

for （i=0;i<n;i=i+1） printf （ "%d "，a[i]）; }

3.3 插入排序算法特点

插入排序的算法特点：每趟从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。也可进行升序或降序排序。

4.结束语

（1）分析冒泡排序的效率，若初始序列为“正序”序列，则只需要进行一趟排序，在排序过程中进行n-1次关键字间的比较，并且不移动记录;反之，如果初始数据为“逆序”序列，则需要进n-1趟的排序，需进行n（n-1）/2次比较，并作等数量级的记录移动。因此，总时间复杂程度为O（n2），冒泡排序法稳定，比较次数已知;但速度慢，每次只能移动相邻两个数据，移动数据的次数多。虽然冒泡排序法的算法很简单，但效率较差。

（2）选择排序法在排序过程中与冒泡法比较，所需进行的记录移动的操作次数较少，其最小值为0，最大值为3（n-1） ，不是稳定的排序法。无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为n（n-1）/2，时间复杂程度为O（n2）。

（3）插入排序法在排序过程中，如果遇到初始序列为正序序列，所需进行关键字间比较的次数达最小值n-1，记录不需移动;反之，若初始序列是逆序序列，则总比较次数达最大值（n+2）（n-1）/2，记录移动的次数也达最大值 （n+4）（n-1）/2。插入排序法的总时间复杂程度为O（n2）。

（4）综上所述，通过对三种算法描述的复杂程度、一般情况下该算法的速度、极端情况下该算法的速度等几方面比较分析，插入排序最简单，当序列中的记录“基本有序”或n值比较小时，它是最佳的排序方法。

参考文献

[1]严蔚敏，吴伟民编著.数据结构（C语言版）[M].北京：清华大学出版社，2009：263-288.

[2]谭浩强编著.C语言程序设计（第三版）[M].北京：清华大学出版社，2005.

作者简介：

鄂晶晶（1993―），女，内蒙古呼和浩特人，内蒙古农业大学本科生。

马红旭（1965―），女，黑龙江哈尔滨人，内蒙古师范大学副教授， 研究方向：计算机应用技术。