Quick Select

说明

Quick Select是由quick sort而来，只是它只用了quick sort前面的partition的部分

Average Case O(n) Worst Case O(n^2)

模板思路

每次选取一个Pivot，可以选第一个 两个variable, 一个存比pivot小的数的数量left，一个存比pivot大的数的数量right

初始化（两个指针指向的都是下一个对应的数应该放的地方）

• left=0 从头开始
• right = length-1 从尾部开始

pointer从0开始，遇到right结束，后面的肯定逗比pivot大

while pivot <= right:
    #因为right指向的是比Pivot大的数下一个可以存放的地方，所以应该用<=
    if nums[pivot] < pivot:
        swap(nums, pointer, left)
        pointer += 1 #这里Pointer可以加1，因为left <= pointer这是肯定的，所以前面换过来的数必然<= pivot, 不向前就会死循环
        left += 1
    elif nums[pivot] == pivot:
        pointer += 1
    else:
        swap(nums, pointer, right)
        right -= 1
        #这里的pointer不能加1，因为不确定后面换过来的数的大小，所以要再次判断

Reference

• quickSelect的解释
• programcreek