基本介紹
算法,超快速排序,實驗結果結論,比較其他程式,快速排序,歸併排序數據,遞歸形式排序,8進制,
算法
排序(Sorting), 就是將數據元素(或記錄)的一個任意序列,重新排列成一個按關鍵字有序的序列。 由於排序是計算機科學中一項複雜而重要的技術,無論在系統軟體還是在套用軟體中使用頻率都很高,因此許多專家、學者對排序問題進行了深入的探討,給出了許多時間複雜度僅為 O(N)的高效排序方法[1—5]。基數排序是典型的時間複雜度僅為 O(N)的算法之一，但其算法結構較複雜，對於一些特殊數據要占用大量額外記憶體，故使用頻率並不高。快速排序算法採用分治原則，算法結構簡單,平均性能較佳為 O(NlogN)，因而被廣泛使用。但快速排序算法，在數據部分相等或有序時，時間複雜度最壞為 O(N2)。側重速度穩定的排序算法的時候，往往使用歸併排序或堆排序。
結合快速排序的分治算法結構和基數排序的原則，本文提出超快速排序算法。新算法保留了快速排序算法結構的簡潔性，同時速度穩定且優於快速排序算法和基數排序算法。
1．算法描述與分析
我們首先討論無符號整數的排序.
關於十進制整數的基數排序，假設所有數據的最高位數為 m, 則先根據最高位（m 位） 的數字將數據分成 10 個小組；對於每個小組的數據，根據次高位（m-1 位）的數字將數據分成 10 個小組；……；依此類推，最後根據個位（1 位）的數字將數據分成 10 個小組,依此收集各個小組的數據，便將數據排序。其算法結構較複雜，對於一些特殊數據要占用大量額外記憶體。
二進制整數的基數排序是一個非常特殊的情形，因為只有兩個數字 0 和 1，故每次將數據分成 2 個小組。假設所有數據屬於[0，21+m-1], m 為一整數，則先根據最高位（m 位）的數字將數據分成 2 個小組，分別屬於[0，2m-1]和[2m，21 + m-1]；根據次高位（m-1 位）的數字將[0，2m-1]的數據分成 2 個小組，分別屬於[0，21 - m-1]和[21 - m，2m-1]，將[2m，21 + m-1]的數據分成 2 個小組，分別屬於[2m，2m+21 - m-1]和[2m+21 - m，21 + m-1]；……；這完全類似於快速排序的分治算法結構，因而可以類似於快速排序實現該算法。
下面的算法 1 是遞歸形式的超快速排序算法,。
超快速排序
設待排序數據存儲於數組 a[]，下標範圍為從 low 到 high，所有數據小於 21 + m, 令 k=2m。
bq_sort(int*a,intlow,inthigh,intk){inti,j;intx;//x為臨時變數i=low;j=high;while(i<j){while(a[j]&k&&i<j)j--;while((a[i]&k)==0&&i<j)i++;if(i<j){x=a[j];a[j]=a[i];a[i]=x;}else{if(a[j]&k)i--;elsej++;break;}}if(k>1){if(low<i)bq_sort(a,low,i,k/2);if(j<high)bq_sort(a,j,high,k/2);}}若 n 個待排序數據存儲於數組 a[],下標從 0 到 n-1。假設所有數據小於 21 + m, m為一整數，則調用該算法的形式為：
bq_sort(0,n-1, 2m)。
若 a[i]& 2m為 1,即 a[i]作為二進制,其 m位為 1；反之，若 a[i]& 2m為 0,即 a[i]作為二進制,其 m位為0。第二次以形式
bq_sort(low,i, 21 - m)
調用該算法，即根據 m-1 位來分組 a[low]到 a[i]的數據。
來自自然界和社會的數據都有一定的變化範圍,例如年齡和經濟數據等。另外, 計算機處理的數據也有字長的限制,因而可以假設所有數據小於 21 + m, m為一整數。如果關鍵字數據類型為字長 16 比特的整數類型，則 m 最大為 15。在數據分布不均勻的情況，可能出現某個小組數據個數小於 2，或者根據最低位分組後仍有多個相等數據，兩種情況下超快速排序算法都會終止相應的遞歸，因而其最壞時間複雜度為 O(N(m+1))=O(N)。
一般的基數排序算法結構較複雜，分配和收集數據時需要占用大量額外記憶體。超快速排序算法最多需要存放 m-1 次遞歸調用的變數，不需要其他額外記憶體。
實驗結果結論
表 1 是對快速排序，歸併排序，基數排序（8 進制）和超快速排序用 C 語言在 Celeron2.0G 上做的一個比較,表中同一列分別為用快速排序，歸併排序，基數排序（8 進制）和超快速排序處理同樣數量的隨機數據(由 RAND 函式產生)所用時間,單位為毫秒 ms.
數據個數 | 20,000 | 200,000 | 2,000,000 | 20,000,000 |
快速排序 | 4 | 42 | 466 | 13608 |
歸併排序 | 4 | 52 | 573 | 6191 |
基數排序(8 進制) | 4 | 32 | 400 | 110000 |
超快速排序 | 4 | 32 | 297 | 2978 |
實驗表明, 算法 1 實現的超快速排序算法不但繼承了基數排序速度穩定的優點，而且其速度明顯快於快速排序、歸併排序和基數排序(8 進制)。由此看來，超快速排序算法是名副其實的。
對於有符號整數,在調用 bq_sort 之前, 首先根據符號位將所有數據分成兩部分, 只是符號位為1 的數據放在前面, 符號位為 0 的數據放在後面，然後再分別調用 bq_sort 即可。在計算機中，副整數是以補碼形式存放的，因而 bq_sort 最終將所有數據按由小到大順序排序。
對於浮點型數據，容易轉換為整數，然後可以使用超快速排序。
對於非數字型數據，如英文單詞的排序，可以先將英文單詞截成長度為 5 的等長字元串（長度小於 5 時用空格補齊） ，令空格，A，B，…，Z 分別對應 0，1，2，…，26，則等長字元串即對應 27 進制整數。使用超快速排序算法排序後，對應的英文單詞已經基本有序，只有長度大於 5 的英文單詞可能未排序。再使用簡單插入排序算法（該算法當數據基本有序時速度相當快）直接排序即可。
比較其他程式
快速排序
q_sort(int *a , long low, long high)
{
long i,j;
int x;
i=low; j=high;
x=a[i];
while(i<j)
while(a[j]>=x && i<j) j--;
a[i]=a[j];
while(a[i]<=x && i<j) i++;
a[j]=a[i];
}
a[i]=x;
if(i–low>1) q_sort(a,low,i-1);
if(high –j>1) q_sort(a,j+1,high);
}
歸併排序數據
下面的算法將一維數組 t2[]中前後向鄰的兩個有序序列歸併為數組 t1[]中一個有序序列。
merge(int *t2,int *t1,int low, int m, int high)
{
int i,j,k;
i=k=low; j=m+1;
while(i<=m && j<=high)
{
if(t2[i]<=t2[j]) t1[k++]=t2[i++];
else t1[k++]=t2[j++];
}
while(i<=m ) t1[k++]=t2[i++];
while(j<=high ) t1[k++]=t2[j++];
}
遞歸形式排序
m_sort(int *a, int *t1,int *t2, int low, int high)
{
int m;
if(low==high && t1!=a) t1[low]=a[low];
if(low<high)
{
m=(low+high)/2;
m_sort(a,t2,t1,low,m);
m_sort(a,t2,t1,m+1,high);
merge(t2,t1,low,m,high);
}
}
8進制
b8q_sort(long low,long high,int m)
{
long i,j,k;
int x;
int start[8],cur[8];
for(i=0;i<8;i++)
start[i]=cur[i]=-1;
for(i=low;i<=high; i++)
{
x=(a[i]>>m)%8;
if(start[x]==-1)
{
start[x]=i;
cur[x]=i;
}
else
{
b[cur[x]]=i;
cur[x]=i;
}
}
for(i=0;i<8;i++)
b[cur[i]]=-1;
j=low;
for(i=0;i<8;i++)
{
k=start[i];
start[i]=j;
while(k>-1)
{
c[j]=a[k];k=b[k];j++;
}
for(i=low;i<=high; i++) a[i]=c[i];
if(m)
{
for(i=0;i<7;i++)
if(start[i+1]-start[i]>1) b8q_sort(start[i],start[i+1]-1,m-3);
if(high-start[7]>0 ) b8q_sort(start[7],high,m-3);
}
}
