使用许多相等的值对数组进行排序java

Question

如果我有一个数组,其中近90%的值是相等的,我想对它进行排序.我应该使用哪种最好的分类方法？

Answer 1

如果数组中有很多重复项，则可以使用不同的方法对其进行排序。对于这个 IMO，自平衡二叉树（如 AVL 或红黑树）将是比任何其他排序算法更好的方法。

\n\n

这个想法是扩展树节点以也具有键的数量。

\n\n

class Node {\n   int key;\n   Node left, right;\n   int count;  // Added to handle duplicates\n   // Other tree node info for balancing like height in AVL\n}\n

\n\n

下面是使用 AVL 树的完整算法。

\n\n

\n

1) 创建一个空的 AVL 树，并将 count 作为附加字段。

\n\n

2) 遍历输入数组并对每个元素 \xe2\x80\x98arr[i]\xe2\x80\x99 执行以下操作

\n\n

   a) If arr[i] is not present in tree, then insert it and initialize count as 1\n\n   b) Else increment its count in tree.\n

\n\n

3）对树进行中序遍历。在进行 inorder 操作时，将每个键的\n count 次放入 arr[] 中。

\n

\n\n

第二步需要O(n Log m)时间，第三步需要O(n)时间。所以总体时间复杂度是O(n Log m)，其中m是不同元素的数量。

\n\n

这里给出了详细的解释和实现：Geeks for Geeks

\n