提供资料下载的网站如何建设,项目网站开发,小江网站建设,wordpress交流题目#xff1a;https://www.acwing.com/problem/content/description/787/对应视频讲解#xff1a;https://www.acwing.com/video/227/题目描述注意本题数据已加强。快速排序过程中#xff0c;如果每次取区间起点或者终点作为分界点#xff0c;则会超时。分界点换成随机值…题目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假设把最左侧的数作为枢轴值/基准值即x3【但由于本题数据已增强在代码里只能取区间中点或随机值作为分界点若取区间起点/终点会超时】枢轴值/基准值用来将整个序列分为两个部分再分别进行快速排序确定枢轴值后从左往右移动i若i指向的数小于x则一直移动直到遇到≥x的数停止。很显然上来的3就xi停在3的位置同理从右往左移动j若j指向的数大于x则一直移动直到遇到≤x的数停止。很显然52j左移移到3时停止。如下[3, 1, 2, 3, 5]i j交换i和j指向的两个数数组变为 [3, 1, 2, 3, 5]由于交换的是3和3数组不变。两个指针分别往中间移动一位如下[3, 1, 2, 3, 5]i ji指向13右移23右移遇到3时停止j指向2不满足3停止在2的位置如下[3, 1, 2, 3, 5]j i 由于此时两指针已经彼此穿过故不能交换两个数再以j指向位置作为分界对其左右两部分分别进行快速排序首先看左侧[3, 1, 2] 都≤3枢轴值为区间起点3指针i指向3指针j指向2i指向3不是3的故i停在该位置j指向2不是3的故j停在该位置交换两数数组变为 [2, 1, 3]同时两指针均往中间移动一位都指向1i指向1满足3右移一位指向3j指向1不满足3停止。如下[2, 1, 3]j i 同理此时两指针已经彼此穿过不能交换两个数。再以j为分界划分为 [2, 1] 和 [3]对于 [2, 1]枢轴值为区间起点2i指向2并停止j指向1并停止交换两数变为 [1, 2]。两指针均往中间移动一位彼此穿过跳出循环返回 [1, 2][3] 只有一个数不需要排序直接返回综上左半部分最终返回 [1, 2, 3]再看右侧[3, 5] 都≥3枢轴值为区间起点3指针i指向3指针j指向5i指向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, right1, arr[(leftright) // 2] # 左指针 右指针 分界点(中间值向下取整)while i j :i1j-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, j1, 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中的每个成员以字符,分隔开 再拼接成一个字符串
