时间戳

首页 > 解决方案 > 对具有许多相等值的数组进行排序java

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

问题描述

如果我有一个数组，其中近 90% 的值是相等的，我想对它进行排序。我应该使用什么最好的排序方法？

标签： javaalgorithmsorting

解决方案

如果数组中有很多重复项，则可以使用不同的方法对其进行排序。对于这个 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) 创建一个空的 AVL 树，并将计数作为附加字段。

2) 遍历输入数组并对每个元素 'arr[i]' 执行以下操作</p> 

   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) 对树进行中序遍历。在做 inorder 时，将每个键的计数时间放在 arr[] 中。

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

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

推荐阅读