快排tips
首先,背过快排模板之后,完成一个快速排序是毫无问题的,但是其中选择分界值是有讲究的;
最开始因为while(i < j)
的限制认为跳出while循环时肯定是i == j
,那么递归时左右两区间的端点取i还是j是无所谓的;即认为quick_sort(q, l, j); quick_sort(q, j+1, r)
或者 quick_sort(q, l, i); quick_sort(q, i+1, r)
是等价的
但是,经过运行,发现端点值的选择和分界值的选择息息相关,如果选择了错误的端点值,那么就会陷入死循环!
两者之间要求如下:
如果分界值x选择左侧端点值q[l]
,那么递归时的端点就须为quick_sort(q, l, j); quick_sort(q, j+1, r)
,即用j,选了左侧端点值作为分界值,那么递归就用右侧的j
如果分界值x选择右侧端点值q[r]
,那么递归时的端点就须为quick_sort(q, l, i - 1); quick_sort(q, i, r)
,即用i,选了右侧端点值作为分界值,那么递归就用左侧的i-1
i和j的选择有些类似对称
此类的验证也很简单,只需要选择数组{1, 2}
即可简单验证!