算法学习笔记(4):计数排序

在宿舍呆着无聊接着在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],