# 以 A[r] 的值为基准，分割数组 A 的区间 [l, r]
partition(A, l, r):
    p ← l
    i ← p-1
    for j ← p to r-1:
        if A[j] < A[r]:
            i ← i+1
            swap(A[i], A[j])

    i ← i + 1
    swap(A[i], A[r])
    return i

# 分割有 N 个元素的整个数组 A 时的使用示例
q ← partition(A, 0, N-1)