在宿舍呆着无聊接着在hackerrank上刷水题。这道题由于排序的依据是一定范围内的整数，所以用计数排序效率应当不错。

说到计数排序，实际上思路也很常见。最常见的一个例子就是比赛或者是考试的时候要进行排名。

比如某班有3名同学考了100分，2名同学考了99分，5名同学考了98分。那么很明显，比99分高的同学一共有3名，所以考99分的同学只能是第4名了。

计数排序大概就是做了个数数每个元素前面有多少元素这个事情。先统计最高分多少分，然后依次统计各个分数的学生个数，然后以此叠加就可以统计出前面有多少个学生了。

而且由于不同分数段的学生是按照原顺序放置到新数组中的，所以在原数组中的顺序并不会被打乱，即这个算法是稳定的。这也是为什么这道题可以用计数排序解，因为并不会打乱文本的顺序。

顺便一提，这道题中的最大值max()的复杂度应该是，所以总运行时间应该是。因为计数排序并不涉及到不同元素之间的比较，即不是比较排序，所以的下界并不适用于计数排序。

最后附上这道题的一个无脑解。

# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
ar = []
idx = []
out = [None]*n
for _ in range(n):
    ar.append(raw_input().split())
    ar[-1][0] = int(ar[-1][0])
    idx.append(ar[-1][0])
    if _<n/2:
        ar[-1][1] = "-"
countlist = [0]*(max(idx)+1)
for item in ar:
    countlist[item[0]]+=1
for i in range(len(countlist)-1):
    countlist[i+1]+=countlist[i]
for item in reversed(ar):
    out[countlist[item[0]]-1]=item
    countlist[item[0]]-=1
for item in out:
    print item[1],