C 整数数组排序

Question

如果我有一个像这样的 int[3] 数组:

score_list[3] = [ 1, 2, 0]

数组中的每个位置都对应一个特定的文档编号:

score_list[0] = D1
score_list[1] = D2
score_list[2] = D3

按降序对数组进行排序的最简单方法是什么，跟踪每个移动的 int 的位置

哪里(排序后):

score_list[3] = [ 2, 1, 0]

和

score_list[0] = D2
score_list[1] = D1
score_list[2] = D3 

我只需要按降序打印，而不是实际重新排列int数组，所以:

for (int i=0; i<3; i++)
{
    if (score_list[0] > score_list[1] && score_list[2])
        printf("D%d-%d",i, score_list[0]);
    if (score_list[1] > score_list[0] && score_list[2])
        printf("D%d-%d", i, score_list[1]);
    if (score_list[2] > score_list[0] && score_list[1])
        printf("D%d-%d", i, score_list[2]);
}

会先打印最大的数字，然后我会比较最后两个，我只是觉得这花费的时间太长，必须有更有效的方法

Answer 1

您可以使用 marker (interface) design pattern 解决这个问题.
通过在每次获得最大值时在数组中记录访问索引，让我先定义解决方案结构，然后我将遍历它:

1. 制作一个与score_list 大小相同的新数组，我们称该数组为marker
2. 在for循环中，您将进行另一个循环来检查最大分数，同时检查标记数组中最大分数的位置是否为0。

样本运行:
在 i=0
在 score_list 上循环，找到 marker == 0 的最大分数，打印它，然后为该分数放置 marker = 1。
在 i=1
您将执行相同的操作，但现在从列表中排除了一个位置

这是一个示例代码，说明如何操作:
请注意:这段代码不是可运行的(而且它也没有优化 O(n^2))，我写它只是为了解释。

int max = -1;
int doc = -1; 
int marker[3] = {0, 0, 0};
for (i=0; i<3; i++)
{
    max = -1;
    for (j=0; j<3; j++)
    {
        // skip this location if it is already printed
        if (marker[j] == 1)
            continue;

        if (score_list[j] > max)
        {
            doc = j;
            max = score_list[j];
        }   
    }

    // this doc will not appear again in the inner for loop (j-loop)
    marker[doc] = 1;

    // print the document with the score
    printf("D%d-%d",doc, max);
}