例如:int A[] = {3,2,1,2,3,2,1,3,1,2,3};
如何有效地对这个数组进行排序?
这是为了求职面试,我只需要一个伪代码。
最佳答案
如何排序的有前途的方式似乎是 counting sort 强>。值得一看this lecture由理查德·巴克兰 (Richard Buckland) 撰写,尤其是 15:20 的部分。
类似于计数排序,但更好的方法是创建一个表示域的数组,将其所有元素初始化为 0,然后遍历数组并对这些值进行计数。一旦知道域值的这些计数,就可以相应地重写数组的值。这种算法的复杂度为 O(n)。
这是具有我描述的行为的 C++ 代码。但它的复杂度实际上是 O(2n):
int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};
// count occurrences of domain values - O(n):
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
domain[A[i]]++;
// rewrite values of the array A accordingly - O(n):
for (int k = 0, i = 1; i < 4; ++i)
for (int j = 0; j < domain[i]; ++j)
A[k++] = i;
请注意,如果域值之间存在很大差异,则将域存储为数组是低效的。在这种情况下,最好使用 map (感谢 abhinav 指出)。这是使用 std::map
的 C++ 代码用于存储域值 - 出现次数对:
int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;
// count occurrences of domain values:
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
keyItr->second++; // next occurrence
else
domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}
// rewrite values of the array A accordingly:
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
for (int j = 0; j < i->second; ++j)
A[k++] = i->first;
(如果有一种方法如何在上面的代码中更有效地使用 std::map
,请告诉我)
关于arrays - 排序:如何对包含 3 种数字的数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11067209/