AcWing 785. 快速排序
原题链接
简单
作者:
arthur15
,
2019-09-08 10:54:37
,
所有人可见
,
阅读 1889
python3 代码
def quick_sort(q, l, r):
if l >= r: # 如果左边的位置大于右边或者左边和右边的区间重合了,就说明调整好了
return
x = q[r]
i = l - 1 # 在调整区间的过程中,因为先移动指针,保证移动后可以知道两侧。所以先将指针放到两侧
j = r + 1
while i < j:
while True:
i += 1
if q[i] >= x:
break
while True:
j -= 1
if q[j] <= x:
break
if i < j:
q[i], q[j] = q[j], q[i]
quick_sort(q, l, i-1) # 递归调整区间,注意这里i-1的边界问题,左边的要小于右边,不能有交叉
quick_sort(q, i, r)
if __name__ == '__main__':
n = int(input())
nums = list(map(int, input().split()))
quick_sort(nums, 0, n-1)
for i in range(n):
print('%s '%nums[i], end='')