文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如果分区函数不与最后一个元素交换pivot，为什么Quick Select的速度要慢40倍？

分区函数是快速选择算法（Quick Select）中的一个关键步骤，用于将数组分成两部分，一部分小于等于pivot，一部分大于pivot。在快速选择算法中，通常会选择数组的最后一个元素作为pivot，并将pivot与分区函数返回的索引位置进行交换。

如果分区函数不与最后一个元素交换pivot，而是保持pivot不变，会导致以下几个问题，从而降低算法的速度：

  1. 分区不均衡：在快速选择算法中，通过不断地将小于等于pivot的元素放在左边，大于pivot的元素放在右边，最终将pivot放在正确的位置上。如果不进行交换，pivot的位置将保持不变，这可能导致分区不均衡。例如，如果数组中存在大量小于pivot的元素，而pivot本身是较大的元素，那么在不进行交换的情况下，pivot将一直处于数组的末尾，导致每次分区只能将一个元素放在正确的位置上，而其他元素则需要进行更多的比较和交换操作，从而降低算法的速度。
  2. 递归深度增加：快速选择算法是通过递归的方式进行的，每次递归都会将数组分成两部分，并对其中一部分进行进一步的分区操作。如果不进行交换，pivot的位置将保持不变，这将导致递归深度的增加。因为每次递归只能将一个元素放在正确的位置上，所以需要更多的递归步骤才能完成整个数组的排序。递归深度的增加会导致算法的时间复杂度增加，从而降低算法的速度。

综上所述，如果分区函数不与最后一个元素交换pivot，会导致分区不均衡和递归深度增加，从而降低快速选择算法的速度。因此，在实际应用中，为了获得更好的性能，建议在快速选择算法中将分区函数返回的索引位置与最后一个元素进行交换。这样可以保持分区的均衡性，并减少递归深度，提高算法的速度。

腾讯云相关产品和产品介绍链接地址：

  • 云服务器（CVM）：提供弹性计算能力，满足各类业务需求。详情请参考：https://cloud.tencent.com/product/cvm
  • 云数据库 MySQL 版（CDB）：提供高性能、可扩展的关系型数据库服务。详情请参考：https://cloud.tencent.com/product/cdb
  • 云原生容器服务（TKE）：提供高度可扩展的容器化应用管理平台。详情请参考：https://cloud.tencent.com/product/tke
  • 人工智能平台（AI Lab）：提供丰富的人工智能开发和应用服务。详情请参考：https://cloud.tencent.com/product/ailab
  • 物联网开发平台（IoT Explorer）：提供全面的物联网设备接入和管理服务。详情请参考：https://cloud.tencent.com/product/iothub
  • 移动推送服务（信鸽）：提供高效可靠的移动消息推送服务。详情请参考：https://cloud.tencent.com/product/tpns
  • 云存储（COS）：提供安全可靠的对象存储服务。详情请参考：https://cloud.tencent.com/product/cos
  • 区块链服务（BCS）：提供一站式区块链应用开发和管理服务。详情请参考：https://cloud.tencent.com/product/bcs
  • 腾讯云元宇宙（Tencent Cloud Metaverse）：提供全面的元宇宙解决方案和服务。详情请参考：https://cloud.tencent.com/solution/metaverse
相关搜索:short时间与日期数据结构栈Surge随机问候语摄像头标定手机ROMspilt源代码语言用户表尺寸
相关搜索:
页面内容是否对你有帮助？
有帮助
没帮助

相关·内容

八十一、最快最优的快速排序和优化

「---- Runsen」 ❞ 快速排序 不久前，我在牛客中看到这样一个笑话，面试官让他写一个快速排序，结果他写了一个冒泡排序，虽说不是计算机专业的，还一直说没有写错，都不知道面试官为什么这么PASS。...谓三点取中法，就是每一轮取排序区间的头、尾和中间元素这三个值，然后把它们排序以后的中间值作为本轮的基准值。调整要选取的这三个值的位置。...快速排序的做法是从左向右依次与 pivot 比较，做交换，这样做其实效率并不高。...举个简单的例子，一个数组 [2, 1, 3, 1, 3, 1, 3]，选第一个元素作为 pivot 是2，每次发现比2小的数会引起一次交换，一共三次。...然而，直观来说，其实只要将第一个3和最后一个1交换就可以达到这三次交换的效果。所以更理想的分区方式是从「两边向中间遍历」的双向分区方式，而不是从左到右，当然前提是基准值选择数组的中位数。

62330

快排查找数组中的第K个最大元素

(A, q+1, r) } 归并排序有个merge()函数，这有个partition()函数：随机选择一个元素作为pivot（一般可选择p~r区间的最后一个元素），然后对A[p…r]分区，函数返回pivot...申请两个临时数组X、Y，遍历A[p…r]： 将＜pivot的元素拷贝到X ＞pivot的元素都拷贝到Y 最后将X、Y中数据顺序拷贝到A[p…r] 但若按照此思路，partition()需很多额外内存空间...分区过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4 在经过第一次分区操作之后，两个6的相对先后顺序就会改变。所以，快排不是稳定排序算法。...极端的：数组数据原已有序，如1，3，5，6，8。如每次选择最后一个元素作为pivot，那每次分区得到的两个区间都不均等。需要进行约n次分区操作，才能完成。...选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot，对数组A[0…n-1]原地分区，这样数组就分成三部分，A[0…p-1]、A[p]、A[p+1…n-1]： K 在A[0…p-1]区间查找

4.1K10

    • 排序算法-下（Java语言实现）

    快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。...partition() 分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为 pivot（一般情况下，可以选择 p 到 r 区间的最后一个元素），然后对 A[p...r]分区，函数返回 pivot...我们每次都从未处理的区间 A[i...r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。...因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序不是一个稳定的排序算法。...我们选择数组区间 A[0...n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0...n-1]原地分区，这样数组就分成了三部分，A[0...p-1]、A[p]、A[p+1...n-1]

    43910

    【金九银十】笔试通关 + 小学生都能学会的快速排序

    步骤如下 选择基准（Pivot）: 从数组中选择一个元素作为基准（通常选择第一个元素、最后一个元素或中间元素）。...- `low`: 数组的起始索引（即子数组的第一个元素的索引）。 - `high`: 数组的结束索引（即子数组的最后一个元素的索引）。功能:这是快速排序的主函数，使用递归方法对数组进行排序。...首先判断 low 是否小于 high，以确保子数组至少有两个元素需要排序。如果 low >= high，则函数返回，不进行任何操作。...核心逻辑: let pivot = arr[high];：选择数组中最后一个元素作为基准点（pivot）。 let i = low - 1;：i 指向的是比 pivot 小的元素的最后一个位置。...if (arr[j] < pivot)：如果当前元素 arr[j] 小于 pivot，则将其与 i+1 位置的元素交换，并将 i 加 1。这样就能保证所有小于 pivot 的元素都移动到左侧。

    8210

    文心一言 VS 讯飞星火 VS chatgpt （73）-- 算法导论7.1 4题

    如果要修改QUICKSORT使其以非递增序进行排序，可以考虑以下几种方法: 1.自定义比较函数 QUICKSORT使用的比较函数是比较数组中两个元素的值，然后根据它们的值来决定它们应该排在哪一组子序列里面...，找到当前子数组中最小的元素，然后将它与当前子数组的最后一个元素交换位置，最后递归调用quick_sort函数对左右两侧的子数组进行排序。...具体来说，我们可以先比较数组的第一个元素和第二个元素，如果第一个元素比第二个元素大，就将它们的位置交换，然后再比较第二个元素和第三个元素，以此类推，直到最后一个元素。...，我们首先选出数组的最后一个元素作为枢轴(pivot),然后遍历整个数组，将小于等于pivot的元素放在它的左边，大于pivot的元素放在它的右边，最后返回枢轴的位置。...修改判断条件 array[j] >= pivot，如果一个元素大于等于 pivot，则将其交换到数组的左侧。 这样，修改后的快速排序算法将会按照非递增序进行排序。

    15420

    数据结构与算法 --- 排序算法（三）

    快速排序 来看一下快速排序的算法原理： 算法图解 如果要排序数组中 p 到 r 的数据，那么，我们选择 p 到r之间的任意一个数据作为 pivot （分区点），然后遍历从 p 到 r...终止条件：p \ge r 其中 partition() 分区函数要做的就是随机选择一个元素作为 pivot （一般选择 p 到 r 区间中的最后一个元素），然后基于 pivot 对区间 Arr...[p,r] 进行分区，分区函数返回分区之后的 piovt 的下标。...，那么 partition() 分区函数实现非常简单，直接申请两个临时数组 X 和 Y，遍历目标区间 Arr[p,r] ，小于 pivot 的直接复制到X，大于 pivot 的直接复制到Y，最后按顺序将...每次从未处理区间 Arr[i,r-1] 中取出一个元素Arr[j] 与 pivot 对比，如果小于 pivot ，则将其插入到已处理区间的尾部，也就是下标为 i 的位置。

    25030

    快速排序

    快速排序的步骤：在数组中选定 pivot（分区点） 将小于 pivot 的数字移到 pivot 的左边将大于 pivot 的数字移到 pivot 的右边分别对左右子序列重复前面 3 步3 案例接下来我们通过一个例子来一起看下快速排序的过程...如果右指针指向的元素 >= pivot，则把右边的指针向左移动： , 1, 5, 2, 4 ￪ ￪如果右指针指向的元素 pivot，则左指针指向的元素填入坑中：2, 1, , 5, 4...a[right] = a[left]; } a[left] = pivot; return left;}5 性能分析（时间关系，这部分跳过）因为划分过程涉及交换操作，如果数组中有两个相同的元素...举个例子，比如 1, 2, 3, 4, 5，如果每次选择第 1 个元素作为 pivot，那么每次分区得到的两个区间都是不均等的。

    15420

    浅尝Python快速排序

    从数列中挑出一个元素，称为"基准"（pivot）， 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。...在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。 举个?...def quick_sort(lst): _less = [] # 存储小于基准数的值 _greater = [] # 存储大于基准数的值 # 递归函数一定要有退出条件 if...len(lst) <= 1: return lst # 基准数，直接获取src的最后一个 _pivot = lst.pop() for _item in lst...l = [69, 96, 520, 666, 1314] print(quick_sort(l)) [69, 96, 520, 666, 1314] 如果你对今天的内容还感兴趣的话，何不点个赞再走呢？

    33540

    字节国际支付十连问

    TCP为什么需要四次挥手？三次行不行呢？ 举个生活的例子吧，假设小明和小红打电话聊天，通话差不多要结束时： 小红说，“我没啥要说的了”。小明回答，“我知道了”。...而内核空间则是每个进程都共享的，因此进程之间要通信必须通过内核。 管道：它的本质是内核里面的一串缓存。它传输数据是单向的，这种通信方式效率低，不适合进程间频繁地交换数据。...你平时是如何优化慢SQL的 数据库慢查询主要有这些原因 如果是SQL没加索引，那就加恰当的索引 如果 SQL 索引不生效，那就关注索引失效的十种经典场景（如不满足最左匹配原则等） 关注limit深分页问题...(arr, low, high, k); //将前K个最大的元素返回 return Arrays.copyOf(arr,k); } void quick...} //交换 arr[high]=arr[low]; } //枢纽元素归位 arr[low]=pivot;

    61410

    算法学习：快速排序

    选择基准值（Pivot） 这是算法流程的起点，从数列中精心挑选出一个元素，赋予它一个特殊角色——“基准”（pivot）。...分区函数 function partition(arr, left, right) { // 选择最右侧元素作为基准值pivot const pivot = arr[right]; let...// 如果当前元素小于或等于pivot if (arr[j] <= pivot) { // 交换arr[i]和arr[j]，并将i右移一位，保持i左侧的元素都小于等于pivot...[arr[i], arr[j]] = [arr[j], arr[i]]; // ES6解构赋值进行交换 i++; } } // 最后将pivot（arr...因为插入排序在小数据集上具有较低的常数因子和无需递归的优点，能够快速完成排序，与快速排序形成互补。 3. 尾递归优化 概念阐述：确保递归调用是函数的最后一个操作，便于某些支持该特性的编译器进行优化。

    10810

    排序算法——Golang实现(一)

    排序算法2.1 快速排序（Quick Sort）思想：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后对左右两部分递归地进行快速排序。...不是稳定排序图片代码实现如果要排序数据序列中下标从 low 到 high 之间的一组数据，我们选择 low 到 high 之间的任意一个数据作为 pivot（分区点），假设对应下标是 pivotIndex...快速排序首先要找到分区点 pivot，一般我们会将数据序列最后一个元素或者第一个元素作为 pivot。...假设我们以最后一个元素作为分区点，然后通过两个变量 i 和 j 作为下标来遍历数据序列，当下标 j 对应数据小于 pivot 时，交换 i 和 j 对应的数据，并且将 i 的指针往后移动一位，否则 i...，并返回 基准元素pivot 的位置下标 func partition(arr []int, low, high int) int { // 以当前数据序列最后一个元素作为初始 基准元素pivot

    27351

    快速排序你真的会了吗？

    假如有一个元素集合A： 选择A中的任意一个元素pivot，该元素作为基准 将小于基准的元素移到左边，大于基准的元素移到右边（分区操作） A被pivot分为两部分，继续对剩下的两部分做同样的处理 直到所有子集元素不再需要进行上述步骤...选择第一个或者最后一个 如果待排序数是随机的，那么选择第一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就会产生一个很糟糕的分割。...如何将元素移动到基准两侧 选好基准之后，如何将元素移动到基准两侧呢？通常的做法如下： 将基准元素与最后的元素交换，使得基准元素不在被分割的数据范围 i和j分别从第一个元素和倒数第二个元素开始。...如果是这样的情况，那么实际上不需要把基准元素和最后一个元素交换，而只需要和倒数第二个元素交换即可，因为最后一个元素肯定大于基准，这样可以减少交换次数。...PUSH到栈中，增长速度慢 注意事项 至此，快速排序所有的主要步骤已经介绍完毕。

    61320

    大佬的快速排序算法，果然不一样

    假如有一个元素集合A： 选择A中的任意一个元素pivot，该元素作为基准 将小于基准的元素移到左边，大于基准的元素移到右边（分区操作） A被pivot分为两部分，继续对剩下的两部分做同样的处理 直到所有子集元素不再需要进行上述步骤...选择第一个或者最后一个 如果待排序数是随机的，那么选择第一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就会产生一个很糟糕的分割。...如何将元素移动到基准两侧 选好基准之后，如何将元素移动到基准两侧呢？通常的做法如下： 将基准元素与最后的元素交换，使得基准元素不在被分割的数据范围 i和j分别从第一个元素和倒数第二个元素开始。...如果是这样的情况，那么实际上不需要把基准元素和最后一个元素交换，而只需要和倒数第二个元素交换即可，因为最后一个元素肯定大于基准，这样可以减少交换次数。...PUSH到栈中，增长速度慢 注意事项 至此，快速排序所有的主要步骤已经介绍完毕。

    59820

    Go 语言算法之美—进阶排序

    排序 堆构建完成之后就是排序了，前面提到了堆有一个很重要的特性，那就是堆顶元素就是最大的元素，我们遍历数组的长度，每次都取堆顶的元素（下标为 0 的元素），将其和数组最后的元素交换位置，然后重新将剩下的数据组织成堆...如果要排序一个数组，我们可以从数组中选择一个数据，做为分区点（pivot），然后将小于分区点的放到分区点的左侧，大于分区点的放到其右侧，然后对于分区点左右两边的数据，继续采用这种分区的方式，直到数组完全有序...概念读起来可能有点抽象，这里我画了一张图来帮助你理解整个排序的过程： 上图展示了第一次分区的过程，假设要排序的数组的下标是 p ~ r，我们取数组的最后一个元素 5 做为分区点，然后比 5 小的数字...（注意动图中是选择第一个元素做为分区点的）： 如果使用一个简单的公式来表示快速排序，可以写成这样： int q = partition(data, p, r); quick_sort(data, p,...r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r); 这里有一个 partition 分区函数，它的作用是选择一个分区点，并且将小于分区点的数据放到其左边

    33730

    【排序2】交换排序：让代码更优雅

    交换排序 1、基本思想及特点 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 特点：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。...2、冒泡排序 冒泡排序（Bubble Sort）是排序算法里面比较简单的一个排序。...它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。...快速排序的主要思想可以概括为以下步骤： 1、选择基准元素：从待排序的数组中选择一个元素作为基准元素（通常可以选择数组的第一个元素，但最好的选择是三数取中）。...2、分区：将数组中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，形成两个子数组。 3、递归排序：对基准元素左边的子数组和右边的子数组分别进行递归调用快速排序。

    14910

    经典排序算法的 JavaScript 代码的实现和适用场景总结

    其中 high 指向最后一个位置元素，而 low 指向第一个元素的位置。 low 指向的数据都应该小于基准数值，而 high 指向的数据都应该大于基准数值。...归并排序他是做插入操作不需要做交换和移动。他建立了一个新的空间，专门用来将比较之后的排序的元素存放。提高了排序的速度但是就是消耗了一倍的空间。...创建堆思路如图： data-al-sort-6.png 从右往左，从下往上找到第一个非叶子结点 判断是不是最大堆如果是的话判断下一个，如果不是的话将最大的节点和最小节点交换位置 交换之后还要在看看其他的节点是不是符合最大堆的规则...拿走根节点和最后一个未交换位置的节点进行交换，这个节点就不会再改变位置了，在重复上面的步骤，知道剩下最后一个节点。...快速排序：快排在元素随机的情况下速度最快，但是如果实在大致有序的情况下速度又是最慢的 堆排序：缺点是不太好理解，需要先转堆结构再交换和移动。

    72971

    算法-排序（上）

    交换排序 基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录。...三个指针区分出了四个分区。算法步骤如下： 选择两个轴元素P1、P2。例如图中选择第一个元素aleft =P1，最后一个元素aright=P2。 限定P1<P2（ 如果不是，则交换P1、P2）。...也就是说PartIV的元素全部分散到Part I II III中，最后是三个Part。 将P1放入Part I的最后一个位置，P2放入Part III的前一个位置（或者第一个位置）。...对于数组中一个元素的访问arrayi称为一次扫描。但是对于同一个下标，并且对应的值也不变的话，即使访问多次也只算一次，不管这个访问是读还是写。 为什么只算一次呢？...扫描的元素与缓存未命中相关: 经典快速排序的一个分区步骤只扫描一次，结果是扫描了n个元素。在双轴快速排序的分区中，索引k和g一起扫描一次，但是索引ℓ 第二次扫描最左边的段。

    36610

    用javascript分类刷leetcode-排序算法(图文视频讲解)

    常见排序算法复杂度图片n^2除nlogn在不同数据规模下的结果图片常见排序算法算法可视化来源：http://visualgo.net/冒泡排序：时间复杂度O(n^2)比较相邻元素，如果第一个比第二个大，...则交换他们一轮下来，可以保证最后一个数是最大的执行n-1轮，就可以完成排序图片function bubbleSort(arr) { var len = arr.length; for (var...//设定基准值位置（pivot）当然也可以选择最右边的元素为基准 也可以随机选择然后和最左或最右元素交换 var pivot = left,...== 0) { this.data[0] = last;//交换第一个元素和最后一个元素 this.bubbleDown(0);//bubbleDown操作...n - 1);//函数开始传入的left=0，right= n - 1 return nums[n - k]; //最后找到了正确的位置 也就是n-k等于pivotIndex 这个位置的元素就是第

    43740

    Lucene系列(14)工具类之快速选择算法

    快速选择及其变种是实际应用中最常使用的高效选择算法。 快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。...三者中位数法选择分割点 取第一个，最后一个，中间位置，三个元素的中位数作为分割点。这样对已部分排序的数据依然能够达到线性复杂度。但是在人为构造的特殊数组上，还是会退化成 O(n2)....版本 8.7.0 定义 该类是一个抽象类，它只负责提供快速选择的分割点选择，左右分区, 不负责具体的存储介质，交换算法等。因此它有三个抽象方法，等待子类实现。...pivot 方法 这个方法实现了对 [left,right]，求解中位数的中位数。 image.png 这个所谓的中位数的中位数，理论上很好求解，又是一个递归的方法而已。为什么变复杂了呢？...代码如下： image.png 其中涉及到一个对 5 个以内的元素求中位数并且分区的方法，其实本质上就是直接进行了插入排序，然后取中位数。

    68710

    七大经典、常用排序算法的原理、Java 实现以及算法分析

    为什么 我们将排序的原理和实现排序时用的大部分都是整数，但是实际开发过程中要排序的往往是一组对象，而我们只是按照对象中的某个 key 来进行排序。 比如一个对象有两个属性，下单时间和订单金额。...实现 首先要对下标从 begin 到 end 之间的数据进行分区，可以选择 begin 到 end 之间的任意一个数据作为 pivot（分区点），一般是最后一个数据作为分区点。...如果 j 指针所指的元素大于 pivot 那么 j 后移即可。...优化 由于分区点很重要（为什么重要见算法分析），因此可以想方法寻找一个好的分区点来使得被分区点分开的两个分区中，数据的数量差不多。下面介绍两种比较常见的算法： **三数取中法。...递归可能会栈溢出，最好的方式是使用非递归的方式； 2.5.3. 算法分析 快排不是一个稳定的排序算法。因为分区的过程涉及到交换操作，原本在前面的元素可能会被交换到后面去。

    71810
    点击加载更多

    扫码

    添加站长 进交流群

    领取专属 10元无门槛券

    手把手带您无忧上云

    扫码加入开发者社群

    相关资讯

    热门标签

    更多标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

      腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

      领券