c - 基础 C 快速排序

Question

我在 Knking 示例中遇到快速排序问题。

int split(int a[], int low, int high)
{
    int part_element = a[low];
    
    for(;;)
    {
        while(low < high && part_element <= a[high])
            high--;
        if(low >= high)
            break;
        a[low++] = a[high];
        
        while(low < high && a[low] <= part_element)
            low++;
        if(low >= high)
            break;
        a[high--] = a[low];
        }
    
    a[high] = part_element;
    return high;
}

我想知道为什么条件 if(low >= high) 有 >。永远高点变小，低点变大，有时它们是一样的。为什么这本书在条件中包含 >？我认为 if(low == high) 就足够了。

在什么情况下low可以大于high？

Answer 1

虽然 split 中的代码是真的不能导致 high变得小于low , 使用 >=很有用，因为:

• 例程可以用high调用已经小于 low .例如，如果一个程序过滤了一些事物的列表，并以零事物结束 ¹ 然后尝试使用 quicksort 对空列表进行排序, 它会用 low 来调用它= 0 和 high = −1.² 当发生这种情况时，我们想要 split退出而不做任何修改。
• 使用 >=通常具有与 == 相同的性能;处理器不会为 >= 做任何额外的工作.通常，int值与完全确定关系的单个指令( < 、 = 或 > ，有时也与其他结果)进行比较，并在标志或结果寄存器中报告它们。然后另一条指令根据结果分支。
• 防止错误是一种很好的做法。以防源代码中的某些错误导致 high变得小于low ，我们可能更愿意在做任何进一步的破坏之前退出例程。 (在这种情况下做出哪些决定通常对情况很敏感。)

脚注

¹ 例如，考虑一个房地产搜索引擎，用户已向该引擎请求有关某个城镇待售房屋的信息。该软件可能会从数据库中检索所有此类房屋。然后它可能会应用用户的过滤器，例如消除所有房屋，除了那些拥有三间卧室且价格低于特定价格的房屋。这些过滤器的结果可能是一个空列表。

² 在 the original code , quicksort包含自己的测试，阻止它调用 split与 low大于 high ，所以这个原因不适用于这个特定的调用代码。尽管如此，这对 split 来说是一个很好的设计。用 low 调用时表现良好大于 high .