【正确答案】如果使用常规的排序方法，虽然最好的排序算法的时间复杂度为O(NlOg₂^N)，但是使用常规排序算法显然没有用到数组中有大量重复数字这个特性。如何能使用这个特性呢?下面介绍两种更加高效的算法。
   方法一：AVL树
   这种方法的主要思路为：根据数组中的数构建一个AVL树，这里需要对AVL树做适当的扩展，在结点中增加一个额外的数据域来记录这个数字出现的次数，在AVL树构建完成后，可以对AVL树进行中序遍历，根据每个结点对应数字出现的次数，把遍历结果放回到数组中就完成了排序，实现代码如下：
   # AVL树的结点
   class Node:
   def __init__(self,data):
   self.data=data
   self.left=self.right=None
   self.height=self.count=1
   
   class Sort:
   #中序遍历AVL树, 把遍历结果放入到数组中
   def inorder(self,arr,root,index):
   if root!=None:
   #中序遍历左子树
   index=self.inorder(arr,root.left,index)
   #把root结点对应的数字根据出现的次数放入到数组中
   i=0
   while i＜root.count:
   arr[index]=root.data
   index+=1
   i+=1
   #中序遍历右子树
   index=self.inorder(arr,root.right,index)
   return index
   #得到树的高度
   def getHeight(self,node):
   if node==None:
   return 0
   else:
   return node.height
   #把以y为根的子树向右旋转
   def rightRotate(self,y):
   x=y.left
   T2=x.right
   #旋转
   x.right=y
   y.left=T2
   y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
   x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
   #返回新的根结点
   return x
   #把以x为根的子树向右旋转
   def leftRotate(self,x):
   y=x.right
   T2=y.left
   y.left=x
   x.right=T2
   x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
   y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
   # Return new root
   return y
   #获取树的平衡因子
   def getBalance(self,N):
   if (N==None):
   return 0
   return self.getHeight(N.left)-self.getHeight(N.right)
   """
   如果data在AVL树中不存在, 则把data插入到AVL树中, 否则把这个结点对应的count加1即可
   """
   def insert(self,root,data):
   if root==None:
   return (Node(data))
   #data在树中存在,把对应的结点的count加1
   if data==root.data:
   root.count+=1
   return root
   #在左子树中继续查找data是否存在
   if data＜root.data:
   root.left=self.insert(root.left, data)
   #在右子树中继续查找data是否存在
   else:
   root.right=self.insert(root.right,data)
   #插入新的结点后更新root结点的高度
   root.height=max(self.getHeight(root.left),self.getHeight(root.right))+1
   #获取树的平衡因子
   balance=self.getBalance(root)
   #如果树不平衡, 根据数据结构中学过的四种情况进行调整
   #LL型
   if balance＞1 and data＜root.left.data:
   return self.rightRotate(root)
   # RR型
   elif balance＜-1 and data>root.right.data:
   return self.leftRotate(root)
   # LR型
   elif balance＞1 and data>root.left.data:
   root.left=self.leftRotate(root.left)
   return self.rightRotate(root)
   # RL型
   elif balance＜-1 and data＜root.right.data:
   root.right=self.rightRotate(root.right)
   return self.leftRotate(root)
   return root
   #使用AVL树实现排序
   def sort(self,arr):
   root=None #根结点
   n=len(arr)
   i=0
   while i＜n:
   root=self.insert(root,arr[i])
   i+=1
   index=0
   self.inorder(arr,root,index)
   
   if __name__="__main__":
   arr=[15,12,15,2,2,12,2,3,12,100,3,3]
   s=Sort()
   s.sort(arr)
   while i＜len(arr):
   print arr[i],
   i+=1
   代码运行结果为：
   2 22 3 3 3 12 12 12 15 15 100
   算法性能分析：
   这种方法的时间复杂度为O(NLog₂^M)，其中，N为数组的大小，M为数组中不同数字的个数，空间复杂度为O(N)。
   方法二：哈希法
   这种方法的主要思路为创建一个哈希表，然后遍历数组，把数组中的数字放入哈希表中，在遍历的过程中，如果这个数在哈希表中存在，则直接把哈希表中这个key对应的value加1；如果这个数在哈希表中不存在，则直接把这个数添加到哈希表中，并且初始化这个key对应的value为1。实现代码如下：
   def sort(arr):
   data_count=dict()
   n=len(arr)
   #把数组中的数放入 map中
   i=0
   while i＜n:
   if str(arr[i]) in data_count:
   data_count[str(arr[i])]=data_count.get(str(arr[i]))+1
   else:
   data_count[str(arr[i])]=1
   i+=1
   index=0
   for key,value in data_count.items():
   i=value
   while i>0:
   arr[index]=key
   index+=1
   i-=1
   
   if __name__="__main__":
   arr=[15,12,15,2,2,12,2,3,12,100,3,3]
   sort(arr)
   i=0
   while i＜len(arr):
   print arr[i],
   i+=1
   算法性能分析：
   这种方法的时间复杂度为O(N+MLog₂^M)，空间复杂度为O(M)。

【答案解析】[考点] 如何对有大量重复的数字的数组排序