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