大多数重复元素的数组的快速排序算法？

Question

什么是有效的方法来排序主要是一小组重复元素的数组？也就是说，列表等：

{10，10，55，10，999，8851243，10，55，55，55，10，999，8851243，10}

假设的equal顺序元素无关紧要，什么是好的最坏情况/平均情况算法？

Answer 1

实际上，您可以先遍历数组一次，然后使用散列表计数单个元素出现次数（这是O（n），其中n =列表大小）。然后取出所有独特的元素并对它们进行排序（这是O（k log k），其中k =唯一元素的数量），然后将其展开回O（n）个步骤中的n个元素列表，从哈希表。如果您节省了时间，则可以使用k < <。

Answer 2

IMO Pidgeonhole sort是这类数据的一个很好的例子。我会澄清一点：如果你知道数组中唯​​一元素的数量是合理的，并且你知道有很多重复数据，我会考虑实现类似于计数排序的东西，但是要制作“桶”列表，动态。第一次通过后，你将摆脱重复，然后排序数组没有重复与一些很好的排序算法，然后像计数排序一样的方式恢复排序的数组。

Answer 3

不是最好的算法，但很简单：
您可以将所有内容放在树中，并让树叶成为计数器。这应该是O（n * m），其中n是元素的数量，m是最大元素的大小（通常这是一个常数，但不一定）。然后预先遍历领带，当你点击一片叶子时，输出当前键的counter元素。这应该只需要O（n + p），其中p是特里结构的大小，与n相比应该很小。

Answer 4

我会尝试Counting sort与一些映射功能。 IE浏览器。你不会使用大小等于元素范围的频率数组，而是迭代数组，写下不同的元素，并在映射函数中将它们用于频率数组。

这样算法只有一个额外的迭代和一个映射函数，它应该在一个固定的时间内工作（使用一些哈希表的王）。这种方法的复杂性将是O(n)，这应该是最佳的。在C++

Answer 5

实现基于ALGO由@Antti Huima

• 计数频率，并存储在哈希表中所建议的。
• 散列表中的排序元素。

• 根据频率覆盖具有排序元素的输入数组。

  #include <unordered_map> 
  #include <map> 
  // Modifies input array to a sorted array 
  // Complexity: O(n+(k*log(k))) where 'k' = number of unique elements input array 
  template <typename Datatype> 
  void SortArrayWithDuplicates(std::vector<Datatype>& in_seq) { 
      std::unordered_map<Datatype, int> key_counts_map; 
      // Count freqs O(n) 
      for (const auto& itr: in_seq) 
       key_counts_map[itr] += 1; 
  
      // Sort elements by inserting into a map O(k*log(k)) 
      std::map<Datatype, int> key_counts_sorted_map; 
      for (auto const& itr: key_counts_map) 
       key_counts_sorted_map.insert(std::make_pair(itr.first, itr.second)); 
  
      auto AlwaysTrue = [](Datatype i)->bool{return true;}; 
      auto seq_itr = std::begin(in_seq); 
      // Update input sequence with new sorted values 
      for (auto const& itr: key_counts_sorted_map) { 
       std::replace_if(seq_itr, seq_itr+itr.second, AlwaysTrue, itr.first); 
       seq_itr += itr.second; 
      } 
  }