algorithm qsort - (sunznx) 振翅飞翔
31 October 2019

快排的思路:将区间分成 <=x (D1) ,和 >=x (D2) ,两个区间,设区间长度为 [l, r]len(D1)+len(D2)=len([l,r])

算法:
设指针 i=l, j=r

  1. i 一直递增,直到遇到一个数字 >=x 就停止
  2. j 一直递减,直到遇到一个数字 <=x 就停止
  3. 此时 arr[i]>=x, arr[j]<=x ,把 arr[j] 放到 D1, arr[i] 放到 D2(即交换 i, j 所在的数字)。所有的 D1 满足 <=x ,所有的 D2 满足 >=x

重叠上面的过程直到 i 和 j 相遇,那么 D1 和 D2 区间为所求,继续递归遍历 D1 和 D2 区间

i 和 j 相遇是什么情况:
假设, x=4, arr[i]=5, arr[j]=3