快排
基于分治,不稳定
$$ 时间复杂度:O(nlog_2n) $$
其中if l >= r: return
不能写成if l == r: return
- 确定分界点
(数组值)
q[l]
:递归处理时,不能使用i
q[(l+r)/2]
q[r]
:递归处理时,不能使用j
随机
- 重新划分区间(重点)
- 左边的区间的所有数字小于等于x
- 右边的区间的所有数字大于等于x
- 递归处理左右两段
样例分析
# 3 1 2 3 5
# 初始化 & * x = 2(取中间值)
# 第一次 & * not 3 < 2 左边停下
# 第二次 & * not 2 > 2 右边停下
# 交换后 2 1 3 3 5
# 第三次 &* not 3 < 2 左边停下
# 第四次 * & not 1 > 2 右边停下
# i >= j 不交换,之后需要递归处理
# ------------
# 此时,i = 2, j = 1,递归的边界
# [l, j] 以及 [j + 1, r](闭区间)
# 先看[l, j],为【2,1】,排完序后为【1,2】
# 再看[j + 1, r],排完序后为【3,3,5】
# 排序成功【1,2,3,3,5】
暴力方法
- 申请两个新的数组
- 分别来装小于等于x的数字以及大于等于x的数字
- 然后再分别把两个数组依次导入到q数组里
优美方法
n = int(input())
alist = list(map(int,input().split()))
def quickSort (q, l, r):
if l >= r: return
i = l - 1
j = r + 1
x = q[l + r >> 1]
while i < j:
i += 1
while q[i] < x:
i += 1
j -= 1
while q[j] > x:
j -= 1
if i < j: q[i], q[j] = q[j], q[i]
quickSort(q, l, j)
quickSort(q, j + 1, r)
quickSort(alist, 0, n - 1)
for i in alist:
print(i, end=' ')