計數(shù)排序
學習基數(shù)排序之前首先學習計數(shù)排序。
計數(shù)排序假設每個元素都是在0到k之間的一個整數(shù)。
基數(shù)排序的基本思想,對于每個元素x,如果我們知道了小于x的元素的個數(shù),就可以確定輸出數(shù)組中元素x的位置,那么直接將元素x放到輸出數(shù)組中。比如有3小于x的元素,那在輸出數(shù)組中,x肯定位于第4個位置。
計數(shù)排序的算法用偽代碼描述為:
// 初始化數(shù)組C
for i=0 to k
C[i]=0
// 統(tǒng)計A[j]元素出現(xiàn)的次數(shù),保存到C數(shù)組中
for j=0 to A.length
C[A[j]]=C[A[j]]+1
// 統(tǒng)計小于等于A[j]元素的個數(shù)
for k=0 to k
C[K]=C[K-1]+C[K]
// 將A中的元素放在B中正確的位置
for i=A.length to 0
B[C[A[i]]-1]=A[i]
C[A[i]]=C[A[i]]-1
注:由于有可能有相同元素存在,所以,每次將A[i]元素放入B數(shù)組中,都要將C[A[j]]的值減一,這樣當遇到下一個值等于A[j]的元素時,該元素就能放在輸出數(shù)組中A[j]的前面。
計數(shù)排序的詳細過程如下
計數(shù)排序的關鍵代碼如下
public int[] countSort(int a[], int k) {
int[] b = new int[a.length];
int[] c = new int[k];
for (int i = 0; i
c[i] = 0;
}
for (int i = 0; i
c[a[i]] += 1;
}
for (int i = 0; i
if (i != 0) {
c[i] += c[i - 1];
}
}
for (int i = a.length - 1; i >= 0; i--) {
b[c[a[i]] - 1] = a[i];
c[a[i]] = c[a[i]] - 1;
}
return b;
}
計數(shù)排序的性能
很容易得到計數(shù)排序的時間復雜度為:T(n)=O(k+n),因此當k小于等于n,也就是當k=O(n),k和n同階時,采用計數(shù)排序的時間復雜度為T(n)=O(n)
同時,計數(shù)排序也是一種穩(wěn)定的排序算法。
基數(shù)排序最初是用在打孔卡片制表機上的一種排序算法,由Herman Hollerith發(fā)明,也就是IBM的創(chuàng)始人。
基數(shù)排序從最低為開始來排序的,從低位到高位,按位排序,按位排序必須是穩(wěn)定的。
基數(shù)排序的詳細過程
基數(shù)排序算法描述為
RADIX-SORT(A,d)
for i=1 to d
use a stable sort to sort arrat A on digit i
在這里我們選擇計數(shù)排序。考慮常規(guī)情況,對[0.。.9]之間的數(shù)排序,k=10,且一般有k<
基數(shù)排序的關鍵代碼,這里以數(shù)組排序時按照十進制每位進行比較。
/**
* 基數(shù)排序
* @param result 最終已排序的數(shù)組,共用一個節(jié)省空間
* @param maxLen 待排序的數(shù)組中最大的位數(shù)
*/
public static void radixSort(int[] a,int[] result, int maxLen) {
int flag = 1;
// 保存每輪要排序的位對應數(shù)組a的值
int [] digitArr = new int[a.length];
for(int i=0; i
// 共比較的輪數(shù)
flag *= 10;
// b數(shù)組中對應的裝著a數(shù)組中每位的數(shù),第一輪裝著各位,第二輪裝著十位數(shù)。。.
for (int j = 0; j < digitArr.length; j++) {
digitArr[j]=a[j]%flag;
digitArr[j]=digitArr[j]/(flag/10);
}
countSort(a, digitArr,result,10);
// 每一輪計數(shù)排序完后刷新下一輪要排序的數(shù)組
System.arraycopy(result, 0, a, 0,result.length);
}
}
調(diào)用計數(shù)排序的函數(shù)
/**
* 計數(shù)排序 :對數(shù)組a中的元素按某些位排序
* @param tmp 要參與排序的當前位的值保存在tmp中
* @param result 每次計數(shù)排序后的新的數(shù)組順序
*/
public static void countSort(int a[], int tmp[], int result[], int k) {
int[] c = new int[k];
for (int i = 0; i < c.length; i++) {
c[i] = 0;
}
for (int i = 0; i
c[tmp[i]] += 1;
}
for (int i = 0; i < c.length; i++) {
if (i != 0) {
c[i] += c[i - 1];
}
}
for (int i = tmp.length - 1; i >= 0; i--) {
// 和計數(shù)排序唯一的差別在于賦值的時候用真實的數(shù)據(jù)
result[c[tmp[i]] - 1] = a[i];
c[tmp[i]] = c[tmp[i]] - 1;
}
}
基數(shù)排序的性能
如果基數(shù)排序使用的穩(wěn)定排序算法的時間復雜度為O(n+k),那么基數(shù)排序的時間復雜度為T(n)=O(d(n+k))
很容易理解要循環(huán)d輪,每輪耗時為O(n+k),于是總的耗時為O(d(n+k))
在此基礎上,從2^r進制來看,此時k為2^r,并且一個b位數(shù)要比較b/r輪。于是我們得到T(n)=O((b/r)(n+2^r))
對上式求導可得其最小值。此時r=lgn,此時T(n)=O((b/lgn)n),如果再取b=lgn,這時就能達到最少的運行時間,時間復雜度為T(n)=O(n)
基數(shù)排序也是穩(wěn)定的排序算法
基數(shù)排序
發(fā)布評論請先 登錄
相關推薦
評論