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])
