sorting - 排序数组算法 - 重复值

Question

我有一个包含重复值的整数数组大小 N，但我不知道值的范围。我在这个数组中有 n/logn 不同的值，其余的都是重复的。

有没有办法用 O(n) 的时间复杂度和 O(n/logn) 的内存复杂度对其进行排序？

Answer 1

只需保留键值对

 for(i=0;i<n;i++)
    {
int key = a[i];
//       if value is in map increase vale of this key
// else add key with value 1 
    } 

现在使用合并排序将此地图数据写入输出数组希望这将解决您的问题..

Answer 2

也许你可以使用这个：

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main()
{
    int n=7;

    int v[]={4,1,2,3,2,4,1}; // initial array

    map<int,int>mp;
    vector<int>uni;

    for(int i=0;i<n;i++)
      if(++mp[v[i]]==1) // counting instance of unique values
        uni.push_back(v[i]); // unique value

    sort(uni.begin(),uni.end()); // sorting : O ((n / logn) * logn) = O(n)

    int cur=0;
    for(int i=0;i<uni.size();i++)
    {
        int cnt=mp[uni[i]];
        while(cnt)  // Adding duplicate values
        {
            v[cur++]=uni[i];
            cnt--;
        }
    }

    for(int i=0;i<n;i++) // Printing final sorted array
      cout<<v[i]<<" ";
    cout<<"\n";
return 0;
}

这里uni数组保留唯一值，即最大值n / logn。然后我们使用具有时间复杂度的
stl函数 作为这里的总元素。复杂性将是.sort()O (n * logn)
n = n / lognO ((n / logn) * logn) = O(n)

所以我们看到，上面的方法对内存很O(n)复杂。O(n * logn)

这里map<>用于计算每个不同值出现的次数。

Answer 3

冒泡排序需要 O(n^2) 时间并且几乎不需要内存来执行（除了存储原始数组） - 请参阅http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort。不过，快速排序要快得多 - 请参阅http://rosettacode.org/wiki/Quick_Sort

重复不会影响这些算法中的任何一个

Answer 4

例如，合并排序是一种 O(n*lg(n)) 时间算法，具有 O(n) 空间复杂度。

您可以使用哈希映射将 n/lg(n) 个唯一项提取到它们自己的数组中，并记下每个项出现的次数；这是（预期的）O(n) 时间和 O(n/lg(n)) 空间。现在，您可以在新数组上运行 Mergesort，即：

O(x*lg(x)) 时间 x=n/lg(n) ==
O(n/lg(n) * lg(n/lg(n))) ==
O(n/lg(n) * [lg(n) - lg(lg(n))]) ==
O(n - n*lg(lg(n))/lg(n))
<= O(n) 时间

和

O(x) 空间，x=n/lg(n) ==
O(n/lg(n)) 空间

最后，通过根据哈希图中记录的重复数复制元素，将有序数组扩展为最终结果。