接上一篇文章肄满，還是那個(gè)題目，用基數(shù)排序來實(shí)現(xiàn)智政。不足之處希望各位前輩指正
題目：給定一個(gè)int數(shù)組A及數(shù)組的大小n认罩，請(qǐng)返回排序后的數(shù)組。保證元素均小于等于2000续捂。
測(cè)試樣例：
排序前[1,2,3,5,2,3],6
排序后[1,2,2,3,3,5]
9.基數(shù)排序
<code>
import java.util.*;
public class RadixSort {
public int[] radixSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
radix(A,10,3,n);
return A;
}
private void radix(int[] A, int radix, int d,int n){//傳入的d為3(考慮分解為個(gè)位十位百位)
int[] temp = new int[n];//臨時(shí)數(shù)組
int[] buckets = new int[radix];//radix為10,按10進(jìn)制拆分(10個(gè)桶)
//循環(huán)中rate用于保存當(dāng)前計(jì)算的位,十位時(shí)rate=10
for(int i=0,rate=1;i<d;i++){//
Arrays.fill(buckets,0);//buckets數(shù)組中全部為0
System.arraycopy(A,0,temp,0,n);//將A中元素復(fù)制進(jìn)臨時(shí)數(shù)組緩存
for(int j=0;j<n;j++){
//計(jì)算數(shù)據(jù)指定位上的子關(guān)鍵字
int subKey = (temp[j]/rate)%radix;
buckets[subKey]++;
}
for(int j=1;j<radix;j++){
buckets[j] = buckets[j]+buckets[j-1];
}
//按子關(guān)鍵字對(duì)指定數(shù)據(jù)進(jìn)行排序
for(int m=n-1;m>=0;m--){
int subKey = (temp[m]/rate)%radix;
A[--buckets[subKey]] = temp[m];
}
rate *= radix;
}
}
}
</code>
補(bǔ)充說明：排序算法是否穩(wěn)定指的是數(shù)組中重復(fù)元素在排序前后的相對(duì)位置是否發(fā)生改變垦垂，若不改變則算法穩(wěn)定，否則不穩(wěn)定牙瓢。
穩(wěn)定的排序算法有：冒泡排序劫拗、插入排序、計(jì)數(shù)排序矾克、基數(shù)排序和歸并排序
不穩(wěn)定的排序算法有：選擇排序页慷、快速排序、希爾排序和
