algorithm - 根据分数排序

Question

我有一个包含一组排名的一维数组。例如

0|0
1|2
2|2
3|1
4|0
5|1

(这里显示的第一列是数组索引)

我想这样排名

1|2
2|2
3|1
5|1
0|0
4|0

请注意，当出现平局时，索引保持数字升序。我应该使用哪种算法来执行此操作？

Answer 1

正如其他张贴者所回答的那样，您可能想要一个稳定的排序。稳定的排序算法包括

• Insertion Sort
• Merge Sort
• Bubble Sort

如果让我选择，我可能会选择归并排序，因为它具有最好的复杂性。不过，插入排序可以在小列表上击败它。我记得读过有一种情况，冒泡排序并不可怕，但我忘记了它是什么。

但是，值得注意的是，担心稳定性会排除像快速排序这样的算法，它可能是您的未指定语言在其排序函数中使用的算法。

无论您使用哪种语言，其排序实现都应该能够采用一个函数来比较两个项目并确定哪个项目“更大”。所以你真正需要做的就是写一个函数

• 如果等级相等，则声称具有较大数值索引的项目“更大”
• 如果排名不相等，则声称排名较高的项目“更大”。
• 如果rank和numerical index都相等，则声明它们相等。

这只是使用语言附带的任何排序算法“按字典顺序”对项目进行排序，并消除了对稳定性的需求，假设您可以认为两个项目具有相同的索引是相等的。

此函数遵循的精确协议(protocol)因语言而异。