【AcWing-Python-785】快速排序
题目：https://www.acwing.com/problem/content/description/787/
对应视频讲解：https://www.acwing.com/video/227/
题目描述
注意本题数据已加强。
快速排序过程中，如果每次取区间起点或者终点作为分界点，则会超时。
分界点换成随机值，或者区间中点即可。
解题思路及代码
（一）解题思路及举例
分治策略：将规模为n的原问题分解为规模减半的子问题，分别求解每个子问题，然后把子问题的解进行综合，从而得到原问题的解
举例如下：
给定一个数组，如 [3, 1, 2, 3, 5]
给定两个指针，分别指向数组的最左侧和最右侧的外侧，再将两指针分别往中间移动一位，此时指针i指向3，指针j指向5，即：
[3, 1, 2, 3, 5]i j[3, 1, 2, 3, 5]i j假设把最左侧的数作为枢轴值/基准值，即x=3【但由于本题数据已增强，在代码里，只能取区间中点或随机值作为分界点，若取区间起点/终点，会超时】
枢轴值/基准值：用来将整个序列分为两个部分，再分别进行快速排序
确定枢轴值后，从左往右移动i，若i指向的数小于x，则一直移动，直到遇到≥x的数停止。很显然，上来的3就＞=x，i停在3的位置
同理，从右往左移动j，若j指向的数大于x，则一直移动，直到遇到≤x的数停止。很显然，5>2，j左移；移到3时停止。如下：
[3, 1, 2, 3, 5]i j交换i和j指向的两个数，数组变为 [3, 1, 2, 3, 5]，由于交换的是3和3，数组不变。两个指针分别往中间移动一位，如下：
[3, 1, 2, 3, 5]i ji指向1＜3，右移，2＜3，右移，遇到3时停止；j指向2，不满足＞3，停止在2的位置，如下：
[3, 1, 2, 3, 5]j i 由于此时两指针已经彼此穿过，故不能交换两个数
再以j指向位置作为分界，对其左右两部分分别进行快速排序：
首先看左侧：[3, 1, 2] 都≤3
枢轴值为区间起点3，指针i指向3，指针j指向2
i指向3不是＜3的，故i停在该位置
j指向2不是＞3的，故j停在该位置
交换两数，数组变为 [2, 1, 3]，同时两指针均往中间移动一位，都指向1
i指向1满足＜3，右移一位，指向3；j指向1不满足＞3，停止。如下：
[2, 1, 3]j i 同理，此时两指针已经彼此穿过，不能交换两个数。再以j为分界，划分为 [2, 1] 和 [3]
对于 [2, 1]，枢轴值为区间起点2，i指向2并停止，j指向1并停止，交换两数，变为 [1, 2]。两指针均往中间移动一位，彼此穿过，跳出循环，返回 [1, 2]
[3] 只有一个数，不需要排序，直接返回
综上，左半部分最终返回 [1, 2, 3]
再看右侧：[3, 5] 都≥3
枢轴值为区间起点3，指针i指向3，指针j指向5
i指向3不满足＜3，停止；j指向5，满足＞3，左移一位到3，不满足＞3，停止
此时两指针都指向3，位于一个位置，跳出循环，返回 [3, 5]
综上，右半部分最终返回 [3, 5]
合并左右两部分结果即得到排好序的序列输出：[1, 2, 3, 3, 5]
（二）代码
n = int(input())
nums = list(map(int, input().split())) # 通过map实现类型转换，返回listdef QuickSort(arr, left, right):if left >= right:return arr# 1、确定分界点i, j, x = left-1, right+1, arr[(left+right) // 2] # 左指针 右指针 分界点(中间值，向下取整)while i < j :i+=1j-=1# 左边区间的值放小于x，指针不断右移；右边的相反while arr[i] < x :i += 1while arr[j] > x :j -= 1# 2、调整区间，使得左边区间是<=x的数，右边区间是>=x的数# 移动过后，如果i还是小于j，说明左边或者右边有逆向数据，所以交换if i < j:arr[i], arr[j] = arr[j], arr[i]# 3、递归处理左右两个区间 QuickSort(arr, left, j)QuickSort(arr, j+1, right)QuickSort(nums, 0, n-1)
print(' '.join(map(str, nums)))知识点总结
（一）map()函数
根据提供的函数对指定的序列做映射，返回一个集合
map(function, iterable)参数：
function：接受一个函数名
iterable：接受一个或多个可迭代的序列
把函数依次作用在list中的每一个元素上，得到一个新的list并返回（map不改变原list，而是返回一个新list）
（二）.join()函数
是一个字符串操作函数
str.join(item)参数：
str：字符串/字符
item：一个成员，注意括号里只能有一个成员
例子：
','.join('abc')
# 将字符串abc中的每个成员以字符,分隔开 再拼接成一个字符串