最有效的方法來排序字符串只有2個不同的字符？

Question

如果我有一個字符串，我知道有不超過2個不同的字符，

例如設置：

aab 
abbbbabb 
bbbaa 
aaaaaaa 
aaaa 
abab 
a 
aa 
aaaaa 
aaabba 
aabbbab 

什麼把它們按字母順序的最有效方法是什麼？

產生的有序set：

a 
aa 
aaaa 
aaaaa 
aaaaaaa 
aaabba 
aab 
aabbbab 
abab 
abbbbabb 
bbbaa 

編輯：

我知道我可以只使用一個正常的排序算法（快速排序，歸併排序），但問題是：事實上，有不超過2個不同的字符使其他效率更高？

如果字符串事項的最大長度，我想知道2個不同的場景答案：

1. 字符串的最大長度是相同的字符串的數量（N串進行排序中，n的串的最大長度）

2. 字符串的最大長度是log N，以N作爲串的數目被分類

我可以一也假定所有的字符串都是不同的。

Answer 1

字符串compareTo或compareToIgnoresCase方法將根據被比較的兩個字符串的字母順序返回一個負整數0或一個polsitive整數。試試看。基於比較的只能漸進

Answer 2

一般的排序算法無法達到的效果比O(nlogn)更好。在你的情況下，有一個額外的信息（2個不同的字符），有可能改善這個結果。一個簡單的方法，將產生O(n)結果：

1. 檢查的第一個字符（讓我們將其標記x）。
2. 掃描字符串直到結束
   • 每當x遇到增加的計數器。
   • 遇到的非X形時，（我們將其標記y）首次儲存於專用的可變
3. 比較x和y。 如果x < y'根據計數器和與y 如果x > y填充從開始與y字符串其餘小號的string length-num of x的時隙，其餘與x's的x填充從開始的字符串。