1.快速排序的基本思想——分治

q：无序数组
l：左端点
r：右端点
（1）确定分界点x
常用取法可为q[ l ]，q[ (l + r) / 2 ]，q[ r ]， 随机取等
（2）调整区间
使区间左边的数均小于等于x，区间右边的数均大于等于x
（3）递归处理左右两段区间

2.暴力解法

（1）开辟两个新空间
a[ ]，b[ ]
（2）遍历q[ l - r ]
q[ i ] <= x 存储到a[ ]
q[ i ] >= x 存储到b[ ]
（3）将ab两个数组合并为新数组
a[ ] → q[ ]
b[ ] → q[ ]

3.优美解法

（1）当i指向的数比x小时，i向右移，直到找到一个比x大的数
（2）当j指向的数比x大时，j向左移，直到找到一个比x小的数
（3）交换i、j位置的数，两个指针往前移动一位
（4）直至i、j相遇

4.快速排序Python代码实现

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

Python3：

def quick_sort(nums, l, r):
    if r <= l:
        return
    x = nums[(l + r) // 2]
    i, j = l - 1, r + 1
    while i < j:
        i += 1
        while nums[i] < x:  # 这里用小于号
            i += 1
        j -= 1
        while nums[j] > x: # 这里用大于号
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quick_sort(nums, l, j) # 这里用 j 和 j + 1
    quick_sort(nums, j + 1, r)

n = input()
nums = [int(v) for v in input().split()]
quick_sort(nums, 0, len(nums) - 1)
for n in nums:
    print(n, end= " ")

5.快速选择算法（第k个数）

时间复杂度为 O(n)

基本思路：
SL：左边的数的个数
若 k <= SL，递归Left
若 k > SL，递归Right，注意此时找Right第 k - SL 小的数

6.快速选择算法Python代码实现

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数

输入样例：

5 3
3 1 2 4 5

输出样例：

3

Python3：

def quick_sort(nums, l, r, k): # 和快排相比，多用一个参数k
    if r <= l:
        return
    x = nums[(l + r) // 2]
    i, j = l - 1, r + 1
    while i < j:
        i += 1
        while nums[i] < x:  # 这里用小于号
            i += 1
        j -= 1
        while nums[j] > x: # 这里用大于号
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    sl = j - l + 1 # 左侧数的个数
    if k <= sl: quick_sort(nums, l, j, k) # 这里用j
    else: quick_sort(nums, j + 1, r, k - sl) # 这里记得将新的k，替换为k-sl

a = input().split()
n = int(a[0])
k = int(a[1])
nums = [int(v) for v in input().split()]
quick_sort(nums, 0, len(nums) - 1, k)
print(nums[k-1])