基础 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 and high = −1.² 出现这种情况，我们希望split不做任何修改直接退出
使用>=一般和==有相同的性能；处理器不会为 >= 做任何额外的工作。通常，int 值与完全确定关系的单个指令（<、= 或 > 进行比较，有时还会与其他结果进行比较）并将它们报告在标志或结果寄存器。然后另一条指令根据结果分支。
防止错误是一种很好的做法。万一源代码中的某些错误导致 high 变得小于 low，我们可能希望例程在造成任何进一步损坏之前退出。（在这种情况下做出哪些决定通常对情况很敏感。）

脚注

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

² 在 the original code 中，quicksort 包含自己的测试，以防止它调用 split 且 low 大于high，所以这个原因不适用于这个特定的调用代码。尽管如此，当 low 大于 high.

时，split 表现良好是一个很好的设计。

基础 C 快速排序

fundamental C quicksort

c

quicksort

脚注