algorithm - 按字母出现的顺序对字符串中的字母进行排序？

Question

是否可以在线性时间内按字母出现的顺序对字符串中的字母进行排序？

例如，boyhood 将排序为 boooyhd。

Answer 1

是的，这是一个 O(2n) 的 python 解决方案:

import sys

word = raw_input("Enter string to sort:")
wordDict = {}

for letter in word:
    if letter in wordDict:
        wordDict[letter] = wordDict[letter] + 1
    else:
        wordDict[letter] = 1

for letter in word:
    sys.stdout.write(letter*wordDict[letter])
    wordDict[letter] = 0