有没有更好的方法来实现计数排序

Question

以下代码实现计数排序：一种按O(n(时间复杂度排序的算法，但(可能(内存开销很大。有更好的方法吗？

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <iterator>
int main() {
std::vector<int> arr = { 12,31,300,13,21,3,46,54,44,44,9,-1,0,-1,-1 };
// find the minimum element in the list
int min = arr.at(std::distance(arr.begin(), std::min_element(arr.begin(), arr.end())));
// offset for negative values
for (auto& elem : arr) {
elem -= min;
}
// new max
int max = arr.at(std::distance(arr.begin(), std::max_element(arr.begin(), arr.end())));
std::vector<std::pair<int, int>> vec;
vec.resize(max + 1);
for (const auto& number : arr) {
// handle duplicates
if (!vec.at(number).second) {
vec[number] = std::make_pair(number + min, 0);
}
vec.at(number).second++;
}
std::vector<int> sorted_vec;
for (const auto& pair : vec) {
if (pair.second) {
for (int i = 0; i < pair.second; i++) {
sorted_vec.push_back(pair.first);
}
}
}
std::for_each(sorted_vec.begin(), sorted_vec.end(), [](const int& elem) { 
std::cout << elem << " "; 
});
return 0;
}

Answer 1

1. ，输入A[0:n]，max_element=k，min_element=0，用于计数排序：

• 时间复杂度：O(n+k(
• 空间复杂度：O(k(

你不能得到O(n(时间复杂度，有O(1(空间复杂度。

如果k非常大，则不应使用计数排序算法。

2. 在您的代码中，您使用std:：vector<std:：对<int，int>gt；以存储计数。它将得到O(2*k(空间复杂度。您可以只使用int的数组

像这样：

#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
int main() {
std::vector<int> arr = { 12,31,300,13,21,3,46,54,44,44,9,-1,0,-1,-1 };
// find the minimum element in the list
int min = *std::min_element(arr.begin(), arr.end());
// offset for negative values
for (auto& elem : arr) {
elem -= min;
}
// new max
int max = *std::max_element(arr.begin(), arr.end());
std::vector<int> vec(max + 1, 0);
for (const auto& number : arr) {
vec[number] += 1;
}
std::vector<int> sorted_vec;
for (int num = 0; num < vec.size(); num++) {
int count = vec[num];
for (int i = 0; i < count; i++) {
sorted_vec.push_back(num + min);
}
}
std::for_each(sorted_vec.begin(), sorted_vec.end(), [](const int& elem) { 
std::cout << elem << " "; 
});
return 0;
}