基本的C快速排序

html5 • • 问答

我在 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？

回答

虽然 中的代码确实split不会导致high小于low，但 using>=很有用，因为：

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

脚注

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

2在原代码，quicksort包含自己的测试，以防止它可以通过调用split与low大于high，所以这个原因不与该特定调用代码适用。尽管如此，split当使用low大于high.

以上是基本的C快速排序的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>