2

我最近尝试为一对整数向量实现基数排序（其中仅当第一个元素相等时才考虑第二个元素）。我通过两次应用计数排序来做到这一点——首先是对中的第二个元素，然后是第一个元素。这是我最初实现计数排序的方式：

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here


//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<vector<int> > mat(N);

for (int i=0;i<n;i++)
{
    mat[arr[i]].push_back(i);
}

//array in which the sorted array will be stored
vector<int> arr2;

for (int i=0;i<N;i++)
{
    for(int j=0;j<sz(mat[i]);j++) arr2.push_back(arr1[mat[i][j]]);
}

第一个 for 循环显然在 O(n) 中运行。由于“mat”数组正好有 n 个条目，因此在第二个（嵌套）循环中最多会访问 2n 次。这意味着上述代码的时间复杂度应该是 O(n)。

然后我将这段代码的运行时间与 STL sort()（时间复杂度为 O(nlog(n))）进行比较，方法是在 10^6 个元素的数组上运行它们。令我大吃一惊的是，STL sort() 最终表现得比我实现的基数排序稍好。

然后，我将计数排序实现更改为以下内容：

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here

//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<int> temp(N,0);

for(int i=0;i<n;i++) temp[arr[i]]++;

for(int i=1;i<N;i++) temp[i]+=temp[i-1];

//array in which the sorted array will be stored
vector<int> arr2(n);

for(int i=n-1;i>=0;i--) arr2[--temp[arr[i]]]=arr[i];

这一次，基数排序确实比 STL sort() 快了大约 5-6 倍。这个观察让我想知道为什么我的第一个基数排序实现比第二个运行慢得多，当它们都是 O(n) 时？

4

1 回答 1

1

您正在使用伪线性算法。它的复杂性在O(M)哪里

M = std::max_element(arr.begin(), arr.end())

您无法将其与std::sort复杂性O(N log(N))所在的位置进行比较

N = arr.size()

第二个版本分配temp一次，而push_back第一个版本中的调用可能会导致许多影响性能的分配。

基数排序是一种不同的算法。检查此链接。

于 2013-08-16T20:17:21.547 回答