关于单路快速排序递归终止条件的疑问

Question

老师快速排序递归终止的条件为啥是l>=r,l=r我能理解就是只有一个元素，可以认为自己本身就是有序的就直接return,但是l>r这种情况怎么会出现呢？虽然我验证后知道递归终止条件就是l>r,但是不是明白什么情况下会出现l>r这种情况。

Answer 1

liuyubobobo 2019-05-18 05:20:38

在这三句话中：

int p = __partition(arr, l, r);    
__quickSort(arr, l, p-1 );    
__quickSort(arr, p+1, r);

比如l = 2, r = 3， partition计算出来的p = 2，则：

__quickSort(arr,2, 2-1 );    // 出现l > r
__quickSort(arr, 2+1, 3);

继续加油：）