C语言排序算法的分析和总结.doc

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;iN-1;i++) 　　{ for(j=0;jN-1-i;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()