常用排序算法分析比较

　常用排序算法分析比较

　论文导读：还要掌握解题的算法。应用冒泡排序法时。所以快速排序法属于不稳定性排序。利用直接插入排序法。直接选择排序法。关键词：算法，冒泡排序法，快速排序法，归并排序法，插入排序法，选择排序法

　引言 我们在进行程序设计时，除了要掌握一门程序设计语言外，还要掌握解题的算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。一切问题解决的过程都是有效数据组织的过程，是寻找、设计和实现算法的过程。排序是数据处理中的一项重要操作。要编制一个好的数据排序程序，就要有一个好的排序算法，既运算快又内存开销小。而所谓排序是将一组无序的数据按一定规律进行排列，使其成为有序序列。排序方法很多，应用也很广泛。这里介绍几个常用的排序算法，并对此进行分析和比较。

　1．冒泡排序法 冒泡排序法是一个最简单的交换排序方法，它是利用相邻的两数据相互比较，如果前面数据比后面数据小，则将这两个数据交换位置（大气泡在小气泡上面），然后再以同样方法比较下两个相邻的数据，以此类推，直到所有数据都有序为止。其算法如下：

　void bubblesort(px a[],int n) { int I, j, bjh;

　px tmp; for (I=0;II;j--) if (a[j]{tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; bjh=1; } if (bjh==0) return; } } 应用冒泡排序法时，若数据已有部分排好序，则它可以很快速地完成排序,这也是它的优点；但另一方面，它会反复扫描数据，比较相邻的两个数据，速度不快也没有效率，这是它不足的地方。从上述算法中也可以看出，相同的数值在排序过后其顺序和排序前的顺序是一样的，冒泡排序是属于稳定性排序。

　2.快速排序法 快速排序法也是很有名且最常用的排序方法之一。也属于交换排序的方法。它的基本思想是通常取待排序的第一个记录，把该记录放入最终位置后，整个数据区间被此记录分割成两个子区间。所有关键字比该记录关键字小的放置在前子区间中，所有比它大的放置在后子区间中，并把该记录排在这两个子区间的中间，这个过程也称作一趟快速

　排序。这之后对所有的两个子区间分别重复上述过程，直到每个子区间内只有一个记录为止。论文检测。快速排序算法如下：

　void quicksort(px a[ ],int s, int t) { int I=s,j=t; px tmp; if (sI) j--; if (I=0 &&tmp.key{a[j+1]=a[j]; j--; } a[j+1]=tmp; } } 从算法可以看出，利用直接插入排序法，最少比较 n-1 次，最多比较n(n-1)/2 次，平均比较次数是 n(n-1)/4 次。插入排序过程中数据的位置不发生变化，它属于稳定的排序方法。

　5．选择排序法 选择排序是从待排序的数据中，按指定的规则选出某种元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。它的基本思想是：把数据区划分成两个部分，即有序区和无序区；从无序区中选择关键字最小的记录，将其添加到有序区的尾部；不断重复上述操作，

　直到无序区为空。其算法如下：

　void selectsort(px a[ ],int n) { int I,j,k; px tmp for (I=0;I<=n-1;I++;) { k=I; for (j=I+1;j<n;j++) if(a[j].keyk=j; tmp=a[I]; a[I]=a[k]; a[k]=tmp; } } 直接选择排序法，其关键字的比较次数与各元素原来的排列顺序无关，但元素的移动次数和初始排列顺序有关，所以直接选择排序也属于不稳定排序法。

　结束语 在程序设计中，排序的算法还有多种，上述是平时常用的几种排序算法,并用 C 语言给出算法描述。一般来说，我们常以算法执行的时间作为衡量算法优劣的主要指标。论文检测。不同的排序方法各有优缺点，可适用于不同的场合。比如，当 n 较小时（n<50），可采用插入

　排序、选择排序或冒泡排序，这些排序方法比较简单；当 n 较大时，则采用快速排序、归并排序等；若待排序列的记录序列初始状态按关键字基本有序，则选用插入排序和冒泡排序效率最高。

　由于排序运算在计算机应用中经常使用，非常重要，深刻理解各种排序的基本思想和特点，熟悉排序过程，熟记各种算法的分析结果及分析方法对程序设计人员是很重要的。在实际应用中，我们可以根据实际问题的要求，选用合适的排序方法。

　参考文献：[1]张勇，杨喜权，刘群义.数据结构(M).北京：北京希望电子出版社，2006，8[1]廖荣贵，许正宪，王龙发等.数据结构与算法（M）.北京：清华大学出版社，2004，11