具有条件的结构数组的最省时排序算法

Question

我知道快速排序是最好的排序算法，这也是我的第一个想法。但是如果我有以下情况：

typedef struct{
   char name[35];
   int age;
}person;

如果我有一个包含 N 个元素的 person 类型的数组，并且我想按姓名对 30-40 岁之间的人进行排序。快速排序在这里仍然是最好的吗，因为我们不会对数组中的所有人进行排序，只对年龄在 30 到 40 岁之间的人进行排序。如果是这样，我将如何选择主元（因为选择中间元素不能保证人在正确的年龄范围内）？我还认为合并排序可能是一个不错的选择，因为我可以将数组拆分为 2 个不同的数组并输入条件。

Answer 1

首先要做的是在 30..40 范围内找到 age 的项目 并复制它们 在优化的增长数据结构中。这个数据结构是一个数组，每次没有足够的剩余space（即C++中的std::vector或C中的this）时容量呈指数增长。

这个新数据结构中的每一项定义为：

typedef struct {
   uint32_t name_prefix;
   uint32_t id; /* Assume the number of persons is not bigger than 4 billion */
} person_ref;

其中 name_prefix 包含 person::name 的第一个字符，而 id 包含项目在初始未过滤数组中的位置。假设 person::name 包含 ASCII/ANSI 个字符，例如 (p.name[0] << 24) | (p.name[1] << 16) | (p.name[2] << 8) | p.name[3]。虽然听起来很昂贵，但现代主流处理器仅需一条快速指令即可完成。如果名称有一些额外的限制（例如大写可打印 ASCII 字符），您可以在此前缀中包含更多字符。

然后您可以使用简单的快速排序（或更好：Introsort）对新数据结构进行排序。请注意，qsort 可用于 C，而 std::sort 可用于 C++。比较运算符可以是：

/* For a C++ code, please use references instead of pointers */
bool compare(const person& p1, const person* p2) {
    const uint32_t prefix1 = p1.name_prefix;
    const uint32_t prefix2 = p2.name_prefix;
    return prefix1 < prefix2 || 
           (prefix1 == prefix2 && strcmp(array[p1.id].name, array[p2.id].name) < 0);
}

其中 array 是包含所有未过滤项目的原始数组。

最后，由于 person_ref::id 字段，您可以将项目复制回来。

这种方法很有效，因为通常假定名称的前缀不相等。事实上，比较整数比用 strcmp 比较两个字符串要快得多。此外，处理小项目会使排序算法更快，因为副本成本更低，而且整个数组可以更好地适应快速 CPU 缓存。如果很多前缀相等并且输入数据结构很大，那么最好使用 64 位整数前缀，或者在最坏的情况下将过滤的项目复制到另一个数据结构中（以便更好地使用 CPU缓存）。

如果筛选项的数量很大并且您想要更快的排序，您可以使用线性时间基数排序结合介绍排序，以便对共享相同前缀的人进行排序。

具有条件的结构数组的最省时排序算法

Most time-efficient sorting algorithm for array of struct with conditions

sorting

algorithm

performance