我在 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
, 使用 >=
很有用,因为:
- 例程可以用
high
调用已经小于low
.例如,如果一个程序过滤了一些事物的列表,并以零事物结束 1 然后尝试使用quicksort
对空列表进行排序, 它会用low
来调用它= 0 和high
= −1.2 当发生这种情况时,我们想要split
退出而不做任何修改。 - 使用
>=
通常具有与==
相同的性能;处理器不会为>=
做任何额外的工作.通常,int
值与完全确定关系的单个指令(<
、=
或>
,有时也与其他结果)进行比较,并在标志或结果寄存器中报告它们。然后另一条指令根据结果分支。 - 防止错误是一种很好的做法。以防源代码中的某些错误导致
high
变得小于low
,我们可能更愿意在做任何进一步的破坏之前退出例程。 (在这种情况下做出哪些决定通常对情况很敏感。)
脚注
1 例如,考虑一个房地产搜索引擎,用户已向该引擎请求有关某个城镇待售房屋的信息。该软件可能会从数据库中检索所有此类房屋。然后它可能会应用用户的过滤器,例如消除所有房屋,除了那些拥有三间卧室且价格低于特定价格的房屋。这些过滤器的结果可能是一个空列表。
2 在 the original code , quicksort
包含自己的测试,阻止它调用 split
与 low
大于 high
,所以这个原因不适用于这个特定的调用代码。尽管如此,这对 split
来说是一个很好的设计。用 low
调用时表现良好大于 high
.
关于c - 基础 C 快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65871185/