4.24  如何对有大量重复数字的数组排序

4.24 如何对有大量重复数字的数组排序

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个数组，已知这个数组中有大量的重复的数字，如何对这个数组进行高效地排序？

分析与解答：

如果使用常规的排序方法，虽然最好的排序算法的时间复杂度为O（NlogN），但是使用常规排序算法显然没有用到数组中有大量重复数字这个特性。如何能使用这个特性呢？下面介绍两种更加高效的算法。

方法一：AVL树

这种方法的主要思路是：根据数组中的数构建一个AVL树，这里需要对AVL树做适当的扩展，在结点中增加一个额外的数据域来记录这个数字出现的次数，在AVL树构建完成后，可以对AVL树进行中序遍历，根据每个结点对应数字出现的次数，把遍历结果放回到数组中就完成了排序，实现代码如下：

代码运行结果如下：

2 2 2 3 3 3 12 12 12 15 15 100

算法性能分析：

这种方法的时间复杂度为O（NLogM），其中，N为数组的大小，M为数组中不同数字的个数，空间复杂度为O（N）。

方法二：哈希法

这种方法的主要思路为创建一个哈希表，然后遍历数组，把数组中的数字放入哈希表中，在遍历的过程中，如果这个数在哈希表中存在，则直接把哈希表中这个key对应的value加1；如果这个数在哈希表中不存在，则直接把这个数添加到哈希表中，并且初始化这个key对应的value为1。实现代码如下：

算法性能分析：

这种方法的时间复杂度为O（N+MLogM），空间复杂度为O（M）。