代码之家 › 专栏 › 技术社区 › CodeFusionMobile

自定义排序,是否始终强制0返回升序?

sorting c++

CodeFusionMobile · 技术社区 · 15 年前

前提

出身背景

我有一个体育比赛的列表,我需要按数组排序。由于该数组的填充性质,95%的时间列表将被预先排序,因此我使用改进的冒泡排序算法对其进行排序(因为它接近O(n),几乎排序的列表)。

冒泡排序有一个名为CompareCompetions的助手函数,用于比较两个竞争并返回>如果comp1更大,则为0,<如果comp2更大,则为0;如果两者相等,则为0。比赛首先按优先级字段进行比较,然后按比赛开始时间进行比较,然后按主队名称进行比较。

优先级字段是解决此问题的关键。它是一个包含正数或0的整数。它们被排序为1第一,2第二,以此类推,但0或无效值总是最后一个。
e、 g.优先事项清单
0, 0, 0, 2, 3, 1, 3, 0
1, 2, 3, 3, 0, 0, 0, 0

这对问题很重要,

这是我现有的比较算法。

int CompareCompetitions(const SWI_COMPETITION &comp1,const SWI_COMPETITION &comp2)
{

    if(comp1.nPriority == comp2.nPriority)
    {
        //Priorities equal
        //Compare start time
        int ret = comp1.sStartTime24Hrs.CompareNoCase(comp2.sStartTime24Hrs);
        if(ret != 0)
        {
            return ret; //return compare result
        }else
        {
            //Equal so far
            //Compare Home team Name
            ret = comp1.sHLongName.CompareNoCase(comp2.sHLongName);
            return ret;//Home team name is last field to sort by, return that value
        }
    }
    else if(comp1.nPriority > comp2.nPriority)
    {
        if(comp2.nPriority <= 0)
            return -1;
        else
            return 1;//comp1 has lower priority
    }else /*(comp1.nPriority < comp2.nPriority)*/
    {
        if(comp1.nPriority <= 0)
            return 1;
        else
            return -1;//comp1 one has higher priority
    }
}

问题

更重要的是。。。
是否有更好的方法将0强制到排序顺序的后面?

我想强调的是,这段代码似乎工作得很好,但我想知道是否有一个更优雅或更有效的算法,任何人都可以建议。请记住,优先级几乎总是0,比赛通常按开始时间或主队名称排序,但优先级必须为0 超越另外两个。

7 回复 | 直到 13 年前

MSN 15 年前

if (a==b) return other_data_compare(a, b);
if (a==0) return 1;
if (b==0) return -1;
return a - b;

the_drow 15 年前

您还可以使用如下三元运算符来减少一些代码冗余:

int CompareCompetitions(const SWI_COMPETITION &comp1,const SWI_COMPETITION &comp2)
{

if(comp1.nPriority == comp2.nPriority)
{
    //Priorities equal
    //Compare start time
    int ret = comp1.sStartTime24Hrs.CompareNoCase(comp2.sStartTime24Hrs);

    return ret != 0 ? ret : comp1.sHLongName.CompareNoCase(comp2.sHLongName);
}
else if(comp1.nPriority > comp2.nPriority)
    return comp2.nPriority <= 0 ? -1 : 1;
else /*(comp1.nPriority < comp2.nPriority)*/
    return comp1.nPriority <= 0 ? 1 : -1;
}

看见
我知道这不是你想要的,但也很重要。

AProgrammer 15 年前

如果不是,我会用

int nPriority1 = comp1.nPriority <= 0 ? INT_MAX : comp1.nPriority;
int nPriority2 = comp2.nPriority <= 0 ? INT_MAX : comp2.nPriority;

if (nPriority1 == nPriority2) {
   // current code
} else {
   return nPriority1 - nPriority2;
}

Peter Recore 15 年前

如果可以,修改优先级方案似乎是最优雅的,这样您就可以正常排序了。例如,不是将默认优先级存储为0,而是将其存储为999,并将用户定义的优先级限制为998。这样您就不必再处理这种特殊情况了,您的比较函数可以有一个更简单的结构,没有if的嵌套:

if (priority1 < priority2) return -1;
if (priority1 > priority2) return 1;

if (startTime1 < startTime2) return -1;
if (startTime1 > startTime2) return 1;

if (teamName1 < teamName2) return -1;
if (teamName1 > teamName2) return -1;

return 0;  // exact match!

Evan Rogers 15 年前

我认为您对解决方案的不雅感来自于零优先级异常的重复代码。 The Pragmatic Programmer 说明源中的每一条信息都应该在“一个真实”的位置定义。对于阅读函数的天真程序员来说,您希望异常在一个地方突出,与其他逻辑分离,以便易于理解。这个怎么样?

    if(comp1.nPriority == comp2.nPriority)
    {
        // unchanged
    }
    else
    {
        int result, lowerPriority;
        if(comp1.nPriority > comp2.nPriority)
        {
            result = 1;
            lowerPriority = comp2.nPriority;
        }
        else
        {
            result = -1;
            lowerPriority = comp1.nPriority;
        }

        // zero is an exception: always goes last
        if(lowerPriority == 0)
            result = -result;

        return result;
    }

Carl Manaster 15 年前

int CompareCompetitions(Competition comp1, Competition comp2) {
    int n = comparePriorities(comp1.nPriority, comp2.nPriority);
    if (n != 0)
        return n;
    n = comp1.sStartTime24Hrs.compareToIgnoreCase(comp2.sStartTime24Hrs);
    if (n != 0)
        return n;
    n = comp1.sHLongName.compareToIgnoreCase(comp2.sHLongName);
    return n;
}

private int comparePriorities(Integer a, Integer b) {
    if (a == b)
        return 0;
    if (a <= 0)
        return -1;
    if (b <= 0)
        return 1;
    return a - b;
}

基本上,只需将零行为的特殊处理提取到它自己的函数中,并按排序优先级顺序沿字段迭代,一旦有非零行为,就返回。

Ari 15 年前

只要最高优先级不大于INT_MAX/2,您就可以这样做

#include <climits>

const int bound = INT_MAX/2;
int pri1 = (comp1.nPriority + bound) % (bound + 1);
int pri2 = (comp2.nPriority + bound) % (bound + 1);

bound 并将所有其他优先级降低1。优点是避免了比较,并使代码的其余部分看起来更自然。

针对您的评论,这里有一个完整的解决方案,可以避免95%的情况下的翻译,即优先级相等。但是,请注意,您对这一点的担心是错误的,因为就这种情况的总体复杂性而言,这种微小的开销可以忽略不计,因为同等优先级情况至少涉及对时间比较方法的函数调用,最坏的情况是对名称比较器的额外调用,这肯定至少比你做的比较优先级要慢一个数量级。如果你真的关心效率,那就去试验吧。我预测在这篇文章中提出的最差和最好的建议之间的差异不会超过2%。

#include <climits>

int CompareCompetitions(const SWI_COMPETITION &comp1,const SWI_COMPETITION &comp2)
{
    if(comp1.nPriority == comp2.nPriority)
       if(int ret = comp1.sStartTime24Hrs.CompareNoCase(comp2.sStartTime24Hrs))
          return ret;
       else
          return comp1.sHLongName.CompareNoCase(comp2.sHLongName);

    const int bound = INT_MAX/2;
    int pri1 = (comp1.nPriority + bound) % (bound + 1);
    int pri2 = (comp2.nPriority + bound) % (bound + 1);
    return pri1 > pri2 ? 1 : -1;
}

return (pri1 > pri2) * 2 - 1;

或

return (pri1-pri2 > 0) * 2 - 1;

或(假设2的补码)

return ((pri1-pri2) >> (CHAR_BIT*sizeof(int) - 1)) | 1;

最后评论: 你真的想要吗 CompareCompetitions bool ( true 如果 comp1 是“ >= " comp2 和 false 否则)。这将简化(尽管稍微简化)代码 比较竞争 以及气泡分拣机的代码。另一方面,它会使 比较竞争 不太通用。