import java.util.Iterator;
public class CompareString {
public void countingSort(String[] A,char[] B,int k) { //計數排序
String[] temp = new String[A.length+1];
int[] c = new int[k+1];
int i,j;
for(i = 0; i <= k; i++)
c[i] = 0;
for(j = 0; j < B.length; j++) {
c[B[j]-'a'] = c[B[j]-'a'] + 1;
}
for(i = 1; i <= k; i++)
c[i] = c[i] + c[i-1];
for(j = A.length - 1; j >= 0; j--) {
temp[c[B[j]-'a']] = A[j];
c[B[j]-'a'] = c[B[j]-'a'] - 1;
}
for(i = 1; i <= A.length; i++) {
A[i-1] = temp[i];
}
}
public void radixSort(String[] A,int d) {
ArrayList[] arr = new ArrayList[26];
countingSort(A,divide(A,d),max(divide(A,d))-'a');
for(int i = 0; i < A.length; i++) {
int temp = A[i].charAt(d-1)-'a';
if(arr[temp] == null)
arr[temp] = new ArrayList();
arr[temp].add(A[i]);
}
for(int j = 0; j < 26; j++) { //對各個桶進行插入排序
if(arr[j] != null) {
insert(arr[j]);
}
}
//將各個桶結果進行合並
int count = 0;
for(int i = 0; i < 26; i++) {
if(arr[i] != null) {
Iterator it = arr[i].iterator();
while(it.hasNext()) {
String temp = (String)it.next();
A[count] = temp;
count++;
}
}
}
}
public void insert(ArrayList list) { //插入排序
if(list.size() > 1) {
for(int i = 1; i < list.size() ; i++) {
if(compareTo((String)list.get(i),(String)list.get(i-1))< 0) {
String temp = (String)list.get(i);
int j = i -1;
for(; j >= 0 && compareTo(temp,(String)list.get(j))< 0;j-- )
list.set(j + 1, list.get(j));
list.set(j + 1, temp);
}
}
}
}
int compareTo(String a, String b) { //比較兩個字符串的大小
return a.compareTo(b);
}
public char[] divide(String[] A, int count) { //取數組中每個字符串的第d個字符
char[] B = new char[A.length];
for(int i = 0; i < A.length; i++) {
B[i] = A[i].charAt(count-1);
}
return B;
}
public char max(char[] B) { //求數組當中的最大值
char max = 'a';
for(int i = 0 ; i < B.length; i++) {
if(B[i] > max) max = B[i];
}
return max;
}
public static void main(String[] args) {
CompareString cs = new CompareString();
String[] A = {"apple","hello","dear","clear","day","happy"};
cs.radixSort(A,1);
for(int i = 0; i < A.length;i++)
System.out.print(A[i] + " ");
}
}