1、單循環(huán)排序算法及其改進(jìn)         關(guān)鍵詞  時(shí)間復(fù)雜度; 穩(wěn)定性; 空間復(fù)雜度; 數(shù)據(jù)交換   0  引言    排序算法對(duì)于計(jì)算機(jī)信息處理很重要，一個(gè)好的排序不僅可以使信息查找的效率提高，而且還直接影響著計(jì)算機(jī)的工作效率 。目前，最常見的排序算法有冒泡排序法、選擇排序法、插入排序法、快速排序法等算法。這些排序算法各有自己的優(yōu)缺點(diǎn)，不同的排序算法適應(yīng)不同的情況。就算法的整體性能而言,目前很難提出一種適應(yīng)所有的排序場(chǎng)合的最好的排序算法，每種算法都有自己

2、不同的適用場(chǎng)合 。比較發(fā)現(xiàn)，這些常用的排序算法的設(shè)計(jì)均為雙重甚至多重循環(huán)算法，目前還很少有單重循環(huán)的排序算法。本文將提出一種只需單重循環(huán)即可完成排序的算法,可適用于許多特殊場(chǎng)合。1  算法思想    該算法的基本思想是：采取一趟逐步推進(jìn)式的排序算法，若排序過程中發(fā)生一對(duì)數(shù)據(jù)的交換，則交換后排序過程回退一步，從前一對(duì)數(shù)據(jù)的比較開始繼續(xù)進(jìn)行。以升序?yàn)槔旱趥€(gè)與其后的第+1個(gè)這一對(duì)數(shù)據(jù)比較，如若前者小，則排序不變，然后比較第+1個(gè)和第+2個(gè)；否則(前者大)，第+1個(gè)和第個(gè)數(shù)據(jù)進(jìn)行交換，此時(shí)循環(huán)回退一步進(jìn)行前一對(duì)數(shù)據(jù)的比較，即第-1個(gè)和新交換后的第個(gè)作比較，這兩

3、個(gè)數(shù)字間的比較也是采用同樣的方法推進(jìn)或回退，依次類推進(jìn)行排序的逐步推進(jìn)。凡是兩個(gè)數(shù)字比較大小時(shí)為正常升序的，則比較向前推進(jìn)。凡是遇到比較大小為逆序需交換的情況，均在交換后將比較回退一步再重新開始，最終將實(shí)現(xiàn)單循環(huán)排序成功。3  算法源程序    為更清楚地了解這種單循環(huán)排序算法，以下給出了VC+6.0環(huán)境下寫成的算法示例源程序，該程序?yàn)榘瓷蚺帕校⑶覍?duì)升序排序算法的循環(huán)結(jié)構(gòu)進(jìn)行了解釋說明。#include<iostream.h>#define M  50void main()  int i,n,aM;  cou

4、t<<"輸入計(jì)算的個(gè)數(shù):"  cin>>n;  cout<<"輸入需要排序的"<<n<<"個(gè)正整數(shù):"   for(i=1;i<=n;i+)       cin>>ai;  cout<<"單循環(huán)排序算法排序后:"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; /若為逆序,需要交換數(shù)據(jù),且排序過程回退一步,進(jìn)行前一對(duì)數(shù)據(jù)間的比較。注意,經(jīng)過+和-2,相當(dāng)i=i-1，  

7、;       for(i=1;i<=n;i+)cout<<ai<<' 'cout<<endl;3  復(fù)雜度分析    該算法在空間上不需要附加的輔助空間。在時(shí)間上，當(dāng)待排序數(shù)據(jù)為正序時(shí)。程序?qū)⒁恢毕蚯巴七M(jìn)，排序過程只需要進(jìn)行-1次比較，且不需移動(dòng)任何數(shù)據(jù)記錄，此時(shí)為最優(yōu)狀態(tài)，時(shí)間復(fù)雜度為O(n) ；反之，當(dāng)待排序數(shù)據(jù)為逆序時(shí)為最壞情況，此時(shí)算法需要進(jìn)行(n-1) 2次比較，并進(jìn)行 n(n-1)/2次數(shù)據(jù)交換，時(shí)間復(fù)雜度為O(n2) 。由

8、于此排序方法為順序推進(jìn)，在回退的過程中也未出現(xiàn)相等數(shù)據(jù)的交換，所以此排序算法是穩(wěn)定的。4  算法改進(jìn)    此算法實(shí)現(xiàn)了單循環(huán)排序算法設(shè)計(jì)，在數(shù)據(jù)為基本正序的過程中實(shí)現(xiàn)起來方便快捷。但在逆序或數(shù)據(jù)復(fù)雜的情況下，在循環(huán)結(jié)構(gòu)中，數(shù)據(jù)在一次比較后開始回退，若數(shù)據(jù)比較不斷回退，當(dāng)回退完成后，新一輪的向前推進(jìn)循環(huán)將重復(fù)比較一些已經(jīng)比較過了的數(shù)據(jù)，因此有必要對(duì)回退開始點(diǎn)處的i值進(jìn)行跟蹤保留，以便回退完成后，直接從回退開始點(diǎn)處開始接著向前推進(jìn)余下的循環(huán)，而不用重復(fù)比較回退結(jié)束處到回退開始點(diǎn)之間的已經(jīng)比較過一次的數(shù)據(jù)。其改進(jìn)只需要將上面程序中的：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;    改進(jìn)后的算法在時(shí)間性能上得到了顯著提升。當(dāng)排序數(shù)據(jù)為正序時(shí)，排序過程只需要進(jìn)行 n-1次比較，且不需要移動(dòng)任何數(shù)據(jù)記錄，此時(shí)為最優(yōu)狀態(tài)，時(shí)間復(fù)雜度為O(n) ，這和改進(jìn)前的時(shí)間復(fù)雜度是一致的。但當(dāng)排序數(shù)據(jù)為逆序時(shí)，改進(jìn)前的算法需要進(jìn)行(n-1)2 次比較,并進(jìn)行 n(n-1)/2次數(shù)據(jù)交換；而優(yōu)化后的算法雖然同樣要進(jìn)行(-1)/2次數(shù)據(jù)交換，但只需進(jìn)行 次比較，時(shí)間得以節(jié)省，兩者在最壞情況下的時(shí)間復(fù)雜度均為 O(n2) 。在隨機(jī)的待排序數(shù)據(jù)序列中，改進(jìn)后的算法明顯優(yōu)于優(yōu)化前的算法及冒泡排序法。5  結(jié)論    這種單循環(huán)排序算法設(shè)計(jì)簡(jiǎn)單，易于實(shí)現(xiàn)，對(duì)于基本有序的數(shù)據(jù)排序性能優(yōu)秀，適合數(shù)據(jù)量適中或數(shù)據(jù)量大但基本有序時(shí)使用，而且該算法對(duì)于數(shù)據(jù)排列大都是兩兩錯(cuò)位的排序過程更是接近最優(yōu)算法。并針對(duì)其在逆序或數(shù)據(jù)復(fù)雜時(shí)排序的不足，對(duì)算法進(jìn)行改進(jìn)，改進(jìn)后的雙循環(huán)算法，由于減掉了重復(fù)比較，算法性能得到進(jìn)一步優(yōu)化，可應(yīng)用于更多的排序過程中。參考文獻(xiàn)3 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(語(yǔ)言版).北京:清華大學(xué)出版社,199