java - 对具有许多相等值的数组进行排序java

Question

<分区>

Answer 1

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

想法是扩展树节点，使其也有键数。

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

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

1) Create an empty AVL Tree with count as an additional field.

2) Traverse input array and do following for every element ‘arr[i]’

   a) If arr[i] is not present in tree, then insert it and initialize count as 1

   b) Else increment its count in tree.

3) Do Inorder Traversal of tree. While doing inorder put every key its count times in arr[].

第二步花费 O(n Log m) 时间，第三步花费 O(n) 时间。因此，总体时间复杂度为 O(n Log m)，其中 m 是不同元素的数量。

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