单循环排序算法及其改进

1、单循环排序算法及其改进         关键词  时间复杂度; 稳定性; 空间复杂度; 数据交换   0  引言    排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率 。目前，最常见的排序算法有冒泡排序法、选择排序法、插入排序法、快速排序法等算法。这些排序算法各有自己的优缺点，不同的排序算法适应不同的情况。就算法的整体性能而言,目前很难提出一种适应所有的排序场合的最好的排序算法，每种算法都有自己

2、不同的适用场合 。比较发现，这些常用的排序算法的设计均为双重甚至多重循环算法，目前还很少有单重循环的排序算法。本文将提出一种只需单重循环即可完成排序的算法,可适用于许多特殊场合。1  算法思想    该算法的基本思想是：采取一趟逐步推进式的排序算法，若排序过程中发生一对数据的交换，则交换后排序过程回退一步，从前一对数据的比较开始继续进行。以升序为例：第个与其后的第+1个这一对数据比较，如若前者小，则排序不变，然后比较第+1个和第+2个；否则(前者大)，第+1个和第个数据进行交换，此时循环回退一步进行前一对数据的比较，即第-1个和新交换后的第个作比较，这两

3、个数字间的比较也是采用同样的方法推进或回退，依次类推进行排序的逐步推进。凡是两个数字比较大小时为正常升序的，则比较向前推进。凡是遇到比较大小为逆序需交换的情况，均在交换后将比较回退一步再重新开始，最终将实现单循环排序成功。3  算法源程序    为更清楚地了解这种单循环排序算法，以下给出了VC+6.0环境下写成的算法示例源程序，该程序为按升序排列，并且对升序排序算法的循环结构进行了解释说明。#include<iostream.h>#define M  50void main()  int i,n,aM;  cou

4、t<<"输入计算的个数:"  cin>>n;  cout<<"输入需要排序的"<<n<<"个正整数:"   for(i=1;i<=n;i+)       cin>>ai;  cout<<"单循环排序算法排序后:"for(i=1;i<n;i+)         &#

5、160;            if(ai<=ai+1) continue;       else                               int t=a

6、i;                  ai=ai+1;                  ai+1=t;  if(i!=0) i=i-2; /若为逆序,需要交换数据,且排序过程回退一步,进行前一对数据间的比较。注意,经过+和-2,相当i=i-1，  

7、;       for(i=1;i<=n;i+)cout<<ai<<' 'cout<<endl;3  复杂度分析    该算法在空间上不需要附加的辅助空间。在时间上，当待排序数据为正序时。程序将一直向前推进，排序过程只需要进行-1次比较，且不需移动任何数据记录，此时为最优状态，时间复杂度为O(n) ；反之，当待排序数据为逆序时为最坏情况，此时算法需要进行(n-1) 2次比较，并进行 n(n-1)/2次数据交换，时间复杂度为O(n2) 。由

8、于此排序方法为顺序推进，在回退的过程中也未出现相等数据的交换，所以此排序算法是稳定的。4  算法改进    此算法实现了单循环排序算法设计，在数据为基本正序的过程中实现起来方便快捷。但在逆序或数据复杂的情况下，在循环结构中，数据在一次比较后开始回退，若数据比较不断回退，当回退完成后，新一轮的向前推进循环将重复比较一些已经比较过了的数据，因此有必要对回退开始点处的i值进行跟踪保留，以便回退完成后，直接从回退开始点处开始接着向前推进余下的循环，而不用重复比较回退结束处到回退开始点之间的已经比较过一次的数据。其改进只需要将上面程序中的：if(i!=0) i=i

9、-2；换成以下代码：for(j=i-1;j>0;j-)  if(aj-1<=aj) break;else   int m=aj-1;aj-1=aj;aj=m;    改进后的算法在时间性能上得到了显著提升。当排序数据为正序时，排序过程只需要进行 n-1次比较，且不需要移动任何数据记录，此时为最优状态，时间复杂度为O(n) ，这和改进前的时间复杂度是一致的。但当排序数据为逆序时，改进前的算法需要进行(n-1)2 次比较,并进行 n(n-1)/2次数据交换；而优化后的算法虽然同样要进行(-1)/2次数据交换，但只需进行 次比较，时间得以节省，两者在最坏情况下的时间复杂度均为 O(n2) 。在随机的待排序数据序列中，改进后的算法明显优于优化前的算法及冒泡排序法。5  结论    这种单循环排序算法设计简单，易于实现，对于基本有序的数据排序性能优秀，适合数据量适中或数据量大但基本有序时使用，而且该算法对于数据排列大都是两两错位的排序过程更是接近最优算法。并针对其在逆序或数据复杂时排序的不足，对算法进行改进，改进后的双循环算法，由于减掉了重复比较，算法性能得到进一步优化，可应用于更多的排序过程中。参考文献3 严蔚敏,吴伟民.数据结构(语言版).北京:清华大学出版社,199