【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
假设把最左侧的数作为枢轴值/基准值,即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, 1, 2, 3, 5]i j
i指向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],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]
合并左右两部分即得到排好序的序列输出
(二)代码
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中的每个成员以字符,分隔开 再拼接成一个字符串