字符串排序有很多應用休偶，比如車牌的排序，基因編碼等滑废。今天介紹一種低位優(yōu)先的字符串排序算法，在介紹它之前先介紹另一種算法--鍵索引計數(shù)法袜爪，它是前者的基礎蠕趁。
鍵索引計數(shù)法
適用性：用于小整數(shù)鍵的算法
比如數(shù)組a={1,2,3,4,2,3,4,2,1,3,4,2,3,4}，它里面重復的數(shù)字比較多辛馆，不重復的只有1俺陋，2，3怀各，4，這時就可以用此方法
步驟
-
1术浪、頻率統(tǒng)計
統(tǒng)計各個數(shù)字出現(xiàn)的此時瓢对，這里1出現(xiàn)了2次，2出現(xiàn)了4次胰苏，3出現(xiàn)了4次
4出現(xiàn)了4次硕蛹，并記錄下來，我們用一個5位的數(shù)組記錄硕并。為什么5而不是4呢法焰？接下來你就會知道
-
2將頻率轉化為索引
前面我們記錄了各自數(shù)字的次數(shù)，并用數(shù)組保存倔毙，假設保存的數(shù)組為a[0]=0埃仪，a[1]=2,a[2]=4，a[3]=4陕赃，a[4]=4 這里從1開始計數(shù)卵蛉，而不是從0，并不是為了與排序的數(shù)字對應么库，而是為了計算索引的方便傻丝，任意鍵的起始索引均為所有較小鍵的頻率之和，我們就可以a[i+1]+=a[i]遞推得到诉儒，這樣a[0]=0葡缰，a[1]=2，a[2]=6，a[3]=10泛释，a[4]=14滤愕，這樣第一個數(shù)字（即1）的起始位置為 0，第2個數(shù)字（即 2）的起始位置為2......多一個位置的好處就已經(jīng)體現(xiàn)出來了胁澳，第一個就是用來標記最開始的起始位置的
數(shù)據(jù)分類
得到各個數(shù)字的起始索引该互，接下來就是將原數(shù)組進行歸類，將相同的數(shù)字放在一起韭畸，這里我們用一個臨時的數(shù)組進行記錄回寫回原數(shù)組
最后是將臨時數(shù)組中的值寫會原數(shù)組
代碼實現(xiàn):
public class countSort {
public static void main(String[] args){
int[] nums={2,3,4,1,2,4,3,1,2,2,1};
countSort sort=new countSort();
sort.indecCountIndex(nums);
}
public void indecCountIndex(int[] nums){
int[] count=new int[6];
//計算頻率
for(int i=0;i<nums.length;i++){
count[nums[i]+1]++;
}
//將頻率轉化為索引
for(int i=1;i<count.length;i++){
count[i]=count[i]+count[i-1];
}
//數(shù)據(jù)分類
int[] aux=new int[nums.length];
for(int i=0;i<nums.length;i++){
aux[count[nums[i]]++]=nums[i];
}
//回寫數(shù)據(jù)（我這里是打佑钪恰）
for(int i=0;i<nums.length;i++){
System.out.print(aux[i]+" ");
}
}
}
