假设我们有一个项目列表，每个项目都有（未知）数量的属性。按单个属性排序是一种简单的排序算法。
问题是：如何按所有属性排序相同的列表？
每个属性都有一个权重，因此我们可以使用稳定排序算法首先按最不重要的属性排序，然后按更重要的属性排序，依此类推，但这显然是不高效的。
谢谢。
谢谢。
3个回答
15
SORT BY A,B,C
您在排序内的比较方式将为：
- 比较元素1的A和元素2的A
- 如果大于或小于，则返回结果
- 否则比较B
- 如果大于或小于，则返回结果
- 否则比较C并返回结果
这个方法可以扩展到A..n个标准，只需要使用一个简单的循环即可：
- 对于标准列表中的每个标准
- 比较元素1的标准与元素2的标准
- 如果大于或小于，则返回结果
- 否则继续 // 为了清晰明了
- 返回相等
以上两种方法都假设您的比较函数是Compare(Element1, Element2)。
- Louis Ricci
3
1这也是O(knlogn)的时间复杂度，其中k是属性数量，n是元素数量，与简单地对k次进行排序的时间复杂度相同。 - amit
这个问题在于一个标准 A 比其他所有标准的权重都要高得多。比如说，如果一个学生擅长数学，而我正在寻找加入我的机器人团队的人，但是这个学生在伦理、职业素养、编码能力以及有毒瘾等方面表现很差，但由于数学是起始重要因素，算法会建议最好的学生至少是这个学生，他将成为前几名的学生。 - Muhammad Umer
4@MuhammadUmer - 你需要一个评分算法而不是排序算法。因此，你需要根据你认为优秀的标准为每个学生生成一个分数，然后按照该分数进行排序。 - Louis Ricci
9
创建一个函数f：A1xA2x..->R [即根据优先级和属性为每个元素赋值]。该函数非常依赖于属性[例如，如果属性值在(0,9)范围内，则简单地给出一个值：
遍历列表，计算函数值，并缓存此函数结果，并根据其排序。复杂度将为O(nk+nlogn)，其中k是属性数，n是元素数。
对于每个属性i，Sigma[val(i)*10^prio(i)]]。遍历列表，计算函数值，并缓存此函数结果，并根据其排序。复杂度将为O(nk+nlogn)，其中k是属性数，n是元素数。
- amit
4
1
prio(i) 是第 i 个属性的优先级，其中 i=0 在此示例中最不重要。 - amit1嘿！我刚看到你的回答（虽然已经晚了两年..）我已经试图理解它将近两天了.. 你能否尝试解释一下算法或者给我提供一些参考资料？ - Almog Baku
1@AlmogBaku 我目前正在旅行中。请在10天后提醒我，我会更好地解释。 - amit
2@AlmogBaku 这个想法基本上是给每个属性赋一个数字值，以使属性的重要性在数字本身中占主导地位。例如，如果您有一个具有3个属性
a，b，c的对象，其中a最为重要，而c最不重要，并且每个属性都在[0,9]范围内，您可以给它赋值val(a)*100 + val(b) * 10 + val(c)。因此，如果您有一个a=3，b=0，c=9的对象，则得到的数字为309。现在，您可以使用常规排序算法根据这个数字对所有对象进行排序。 - amit1
大多数排序算法都可以接受一个输入的比较函数，该函数可以组合多个排序标准。
最终，为了能够进行排序，所有元素之间必须存在单一的排序关系（例如，A绝对领先于元素B，或者反之，或者两者相等；关系必须满足传递性/对称性/自反性），因此这意味着在给定有效的比较函数的情况下，必须可以使用一次排序算法进行排序。
- Jason S
2
1这也是O(knlogn)的最坏情况，[k是属性数量，n是元素数量]因为你需要在每次比较中检查k个元素。与使用稳定算法排序k次相同的限制。 - amit
1返回翻译的文本：如果只是指针而不是对所有元素进行k次比较，那么仅返回true的性能可能会更好，因为您不需要为所有元素执行所有k次比较，这在渐近意义下将是相同的[至少对于最坏情况分析]。 - amit
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接