C语言排序算法的分析和总结
开篇：润墨网以专业的文秘视角，为您筛选了一篇C语言排序算法的分析和总结范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:本文具体介绍了C语言当中几种常用的排序方法,并对这些排序方法的基本思想、算法代码、执行过程进行了分析和总结。力求使初学者对于C语言当中遇到的排序问题有个比较清晰的了解。
关键词:冒泡排序;选择排序;直接插入排序;shell排序;快速排序;堆排序
中图分类号: TP312文献标识码:A文章编号:1009-3044(2010)18-5041-03
Summarization and Analysis of Sorting in C Language
LIANG Xu-ling
(Taizhou College, Taizhou 318000, China)
Abstract: This article discusses some of common sorting in C language, and that thebasic thought, algorithm code, sorting process of common sorting were analyzed and summarized. In this way, it will be of a great help for programmers to identify sorting in C language.
Key words: BubbleSort; Straight Insertion Sort; ShellSort; Quicksort; HeapSort
1 概述
数据排序是计算机编程过程中经常会遇到的一个问题,同样C语言中关于排序问题的算法也有多种。本文主要对一些常见的排序算法进行一个归纳总结,方便初学者对这一问题有一个全面的了解。
所谓数据排序,就是将一组无序的数据,按照其中的某个关键字的大小,递增或递减的排列成有序的数据序列。在C语言的学习过程当中,经常会碰到关于整数、浮点数、字符以及字符串的排序问题。一般的排序方法有:冒泡排序、选择排序、插入排序、shell(希尔)排序、快速排序、堆排序等。下面就通过具体的例子,对这些排序方法的基本思想、执行过程、算法代码进行一个总结分析。
2 各种排序算法的分析
2.1 冒泡排序
冒泡排序法是C语言当中最为常见和通用的一种排序方法。
2.1.1 基本思想
在待排序的一组数中,相邻的两个数两两比较后发现它们的顺序与排序要求相反时,就将它们互换(即:如果从小到大排序,则两两比较时,让较大的数往下沉,较小数往上冒)。如此下去,直至最终完成排序。冒泡排序过程中,如果对N个数进行排序的话,需要进行比较的轮数是N-1轮,每轮进行N-1-i次。由于在排序过程中,它的工作看起来像冒泡,所以称作冒泡排序。
2.1.2 算法代码
例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。
该例子用冒泡法实现的代码段如下:
main()
{ int i,j,t,N,aa[5];
aa[5]={8,5,10,7,3};
N=5;
for(i=0;i
{ for(j=0;j
if(aa[j]>aa[j+1])
{ t=aa[j];aa[j]=aa[j+1];aa[j+1]=t; }}
2.1.3 执行过程
第一轮:8,5,10,7,3->5,8,10,7,3->5,8,7,10,3->5,8,7,3,10 (交换3次)
第二轮:5,8,7,3,10->5,7,8,3,10->5,7,3,8,10 (交换2次)
第三轮:5,7,3,8,10->5,3,7,8,10 (交换1次)
第四轮:5,3,7,8,10->3,5,7,8,10 (交换1次)
2.1.4 分析
在程序执行过程中,关系到算法性能的主要因素是循环和交换的次数,次数越多,性能越差。
对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是3+2+1+1=7次。冒泡法的特点是原理简单,但其缺点是交换次数多、效率低。
2.2 选择排序
2.2.1 基本思想
在待排序的一组数中,每轮将首数与后数进行两两比较,按大小进行交换,选出待排序数组中最小(或最大)的一个元素,放在已经排好序的数列的最后。如此下去,直至最终完成排序。冒泡排序过程中,如果对N个数进行排序的话,需要进行比较的轮数是N-1次,每轮从i+1开始到N-1为止。
2.2.2 算法代码
同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。
main()
{ int i,j,t,N,k,aa[5];
aa[5]={8,5,10,7,3};
N=5;
for(i=0;i
{ k=i;
for(j=i+1;j
if(aa[k]>aa[j]) k=j;
if(i!=k)
{ t=aa[i]; aa[i]=aa[k]; aa[k]=t; } } }
2.2.3 执行过程
第一轮:8,5,10,7,3->3,5,10,7, 8(交换1次)
第二轮:3,5,10,7, 8 (交换0次)
第三轮:3,5,10,7, 8-> 3,5,7,10,8(交换1次)
第四轮:3,5,7,10,8->3,5,7,8,10 (交换1次)
2.2.4 分析
对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+0+1+1=3次。选择法的循环过程与冒泡法一致,它定义了作为记号的变量k赋初值为i,依次把a[k]同后面元素比较,若有元素比a[k]小,则将该元素下标赋值给k,使得变量k当中存放的永远是最小元素的下标。最后再a[k]与a[i]交换,这样就比冒泡法省下许多无用的交换,提高了效率。
2.3 直接插入排序
2.3.1 基本思想
在待排序的一组数中,先比较前两个数,按大小顺序排列好,然后每次从后面的无序数中取出第一个元素,把它插入到前面有序数的合适位置,使有序数组仍然有序,把数组元素插完也就完成了排序。
2.3.2 算法代码
同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。
main()
{ int i,j,t,aa[5];
aa[5]={8,5,10,7,3};
N=5;
for(i = 1; i
{t = aa[i];
for (j = i; j > 0 && t < aa[j - 1]; j--)
{aa[j] = aa[j - 1]; }
aa[j] = t; }}
2.3.3 执行过程
第一轮:8,5,10,7,3->5,8,10,7,3(交换1次)
第二轮:5,8,10,7,3 (交换0次)
第三轮:5,8,10,7,3-> 5,7,8,10, 3(交换1次)
第四轮:5,7,8,10,3->3,5,7,8,10 (交换1次)
2.3.4 分析
对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+0+1+1=3次。直接插入排序的特点是算法简单、容易实现。它是采用逐步增加有序元素想法,直至所有元素排列完成。如果待排序数组元素不是特别多的时候,该算法的效率快是较佳的排序方法。但对于大数组,这种算法比较慢就不大适用了。
2.4 shell排序
2.4.1 基本思想
希尔算法的本质是缩小增量排序,是对直接插入排序算法的改进。先取一个小于N的整数p作为第一个增量,将待排序的一组数按增量p分割成多个组,对每个组分别进行一趟直接插入排序。然后缩小增量p的值(一般取其一半)再排序,直到p=1时完成排序。
2.4.2 算法代码
同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。
main()
{ int i,j,t,N,p,aa[5];
aa[5]={8,5,10,7,3};
N=5;
for( p=N/2; p>0; p=p/2)
{ for(i= p;i
{ for(j=i-p;(j >= 0) && (aa[j] > aa[j+p]);j=j-p )
{ t=aa[j];aa[j]=aaj+p];aa[j+p]=t;} } } }
2.4.3 执行过程
第一轮:8,5,10,7,3->8,5,3,7,10 (交换1次)
第二轮:8,5,3,7,10->3,5,8,7,10 (交换1次)
第三轮:3,5,8,7,10->3,5,7,8,10 (交换1次)
2.4.4 分析
对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+1+1=3次。Shell排序的优点是不管待排序数组长度多长,在分组增量p的切割下每个子组的规模都不会太大,然后用直接插入排序效率较高。后来增量p的逐渐递减,分组数逐渐减少,而各组的记录数目逐渐增多,但由于排过序,整个数组的有序性越来越清晰,所以排序的效率依然较高。所以,希尔排序在效率上比直接插人排序有很大的改进。
2.4.5 快速排序
2.4.5.1 基本思想
在待排序的一组数中,先选择其中一个元素作为分隔点(一般选取数组中间的那个元素),然后把比该元素小的数据放在左边,大的放在右边。再按此方法对两边的数据分别再快速排序(也就是递归调用),直到整个数组有序为止。
2.4.5.2 算法代码
同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。
void quick sort(int *s,int i,int j)
{ int left,right,temp, mid;
left=i; right=j; mid=s[(i+j)/2];
do {
while(s[left]
while(s[right]>mid && right>i)right--;
if(left
{ temp=s[left]; s[left]=s[right]; s[right]=temp;left++; right--;}
} while(left
if(left
if(n>i)quick sort(s,i,right); }
main()
{ int aa[5] ={8,5,10,7,3;
quick sort(aa,0,4);}
2.4.5.3 执行过程
第一轮:8,5,10,7,3->8,5,3,7,10 (交换1次)
第二轮:8,5,3,7,10->3,5,8,7,10 (交换1次)
第三轮:3,5,8,7,10->3,5,7,8,10 (交换1次)
2.4.5.4 分析
对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+1+1=3次。快速排序是对冒泡排序的一种本质改进,其优点是运算速度快,数据移动少。缺点是算法稍复杂。快速排序法中关键是对三个参数的设定,即待排序数组元素的起始下标、最后一个元素下标以及分隔元素下标的确定。
3 总结
除了上述分析的五种常见的排序方法外,还有堆排序、归并排序等。在选择排序算法的时候,要根据待排元素数目N的大小以及元素本身的初始状态来做最佳的抉择。如果N数较小,则可采取直接插入排序或选择排序;若数组本身初始状态局部或整体有序时,则可采取冒泡排序或插入排序;若N数较大,则可采取快速排序、堆排序或归并排序。
参考文献:
[1] 谭浩强. C程序设计[M].3版. 北京:清华大学出版社,2005.
[2] 谭浩强,张基温,唐永炎. C程序设计教程[M]. 北京:高等教育出版社,1992.
[3] 马丽娟, 黄勇. C语言数组排序总结[J]. 电脑学习,2008(10):50-51.