使用int向量向量对整数的向量进行排序

Question

我最近试图对整数对向量实施基数排序（其中第二个元素仅在第一个元素相等时才被考虑）。我这样做是通过应用计数排序两次 - 首先对该对的第二个元素，然后到第一个元素。下面是我如何实现计数排序首先：

//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）的时间复杂度，因为它应该有。

然后，我通过在10^6个元素的数组上运行这两个代码，将此代码的运行时间与STL sort（）（它的时间复杂度为O（nlog（n）））进行比较。令我非常惊讶的是，STL排序（）最终表现略好于我的基数排序实现。

然后我改变了我的票样实现以下几点：

//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排序快约5-6倍（）。这个观察让我想知道为什么我的第一个基数排序实现比第二个排序实现运行速度慢得多，当它们都是O（n）时？

Answer 1

您正在使用伪线性算法。它的复杂性是O(M)其中

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

你不能把它比作std::sort其复杂性是O(N log(N))其中

N = arr.size() 

第二个版本分配temp一次，而在第一个版本的push_back通话可能会导致影响性能的很多拨款。

基数排序是一种不同的算法。检查这个link。