quickselect_QuickSelect：使用代码示例解释的快速选择算法
quickselect
什么是QuickSelect？ (What is QuickSelect?)
QuickSelect is a selection algorithm to find the K-th smallest element in an unsorted list.
QuickSelect是一种选择算法，用于在未排序的列表中查找第K个最小的元素。
算法说明 (The Algorithm Explained)
After finding the pivot (a position that partitions the list into two parts: every element on the left is less than the pivot and every element on the right is more than the pivot) the algorithm recurs only for the part that contains the k-th smallest element.
找到枢轴后(将列表分为两部分的位置：左侧的每个元素均小于枢轴，右侧的每个元素均大于枢轴)，该算法仅针对包含第k个部分的部分重复最小的元素。
If the index of the partitioned element (pivot) is more than k, then the algorithm recurs for the left part. If the index (pivot) is same as k, then we have found the k-th smallest element and it is returned. If index is less than k, then the algorithm recurs for the right part.
如果分区元素的索引(枢轴)大于k，则该算法从左侧开始重复。 如果索引(枢轴)与k相同，则我们找到了第k个最小元素，并将其返回。 如果index小于k，则算法在右部分重复执行。
选择伪码 (Selection Psudocode)
Input : List, left is first position of list, right is last position of list and k is k-th smallest element.
Output : A new list is partitioned.quickSelect(list, left, right, k)if left = rightreturn list[left]// Select a pivotIndex between left and rightpivotIndex := partition(list, left, right, pivotIndex)if k = pivotIndexreturn list[k]else if k < pivotIndexright := pivotIndex - 1elseleft := pivotIndex + 1划分 (Partition)
Partition is to find the pivot as mentioned above. (Every element on the left is less than the pivot and every element on the right is more than pivot) There are two algorithm for finding the pivot of partition.
分区是为了找到如上所述的枢轴。 (左边的每个元素都小于轴，右边的每个元素都大于轴)有两种算法可以找到分区的轴。
- Lomuto PartitionLomuto分区
- Hoare Partition霍尔分区
Lomuto分区 (Lomuto Partition)
This partition chooses a pivot that is typically the last element in the array. The algorithm maintains index i as it scans the array using another index j such that the elements lo through i (inclusive) are less than or equal to the pivot, and the elements i+1 through j-1 (inclusive) are greater than the pivot.
该分区选择一个枢轴，该枢轴通常是数组中的最后一个元素。 该算法在使用另一个索引j扫描数组时会维护索引i，以使元素lo至i(包括)小于或等于枢轴，元素i + 1至j-1(包括)大于元素。枢。
This scheme degrades to O(n^2) when the array is already in order.
当阵列已经排列好时，此方案降级为O(n^2) 。
algorithm Lomuto(A, lo, hi) ispivot := A[hi]i := lo for j := lo to hi - 1 doif A[j] < pivot thenif i != j thenswap A[i] with A[j]i := i + 1swap A[i] with A[hi]return i霍尔分区 (Hoare Partition)
Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one less than or equal to the pivot, that are in the wrong order relative to each other.
Hoare使用两个索引，它们从被分割的数组的末端开始，然后彼此靠近，直到它们检测到反转：一对元素，一个大于或等于枢轴，一个小于或等于枢轴，彼此的顺序错误。
The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index. There are many variants of this algorithm.
然后交换倒置的元素。 当索引满足时，算法停止并返回最终索引。 此算法有很多变体。
algorithm Hoare(A, lo, hi) ispivot := A[lo]i := lo - 1j := hi + 1loop foreverdoi := i + 1while A[i] < pivotdoj := j - 1while A[j] > pivotif i >= j thenreturn jswap A[i] with A[j]翻译自: https://www.freecodecamp.org/news/quickselect-algorithm-explained-with-examples/
quickselect
相关文章：
《Linux命令行与shell脚本编程大全 第3版》Shell脚本编程基础---34
以下为阅读《Linux命令行与shell脚本编程大全 第3版》的读书笔记，为了方便记录，特地与书的内容保持同步，特意做成一节一次随笔，特记录如下：转载于:https://www.cnblogs.com/guochaoxxl/p/7894620.html
CSS超出部分隐藏，显示滚动条
实现功能： 固定一个高度，超出该高度的部分就隐藏，并且显示滚动条能上拉下滑滚动 实现代码： height: 500rpx; overflow-x: hidden; overflow-y: scroll; 实现功能： 固定一个宽度，超出该宽度的部分就隐藏…
第二周学习进度
好久的编程实现，居然没有编完整，看来自己需要加班学习了！第二周学习进度如下： 第二周所花时间（包括上课）共计21小时代码量（行）220博客量（篇）4了解到的知识 1.…
如何在C ++中从容器中删除元素
How to remove elements from container is a common C interview question, so you can earn some brownie points if you read this page carefully. 如何从容器中删除元素是C 常见的面试问题，因此，如果仔细阅读此页，可以赚取布朗尼积分。 …
【BZOJ4282】慎二的随机数列 乱搞
【BZOJ4282】慎二的随机数列 Description 间桐慎二是间桐家著名的废柴，有一天，他在学校随机了一组随机数列， 准备使用他那强大的人工智能求出其最长上升子序列，但是天有不测风云，人有旦夕祸福，柳洞一成路过…
git phpstorm 配置
http://jingyan.baidu.com/album/a948d65105faed0a2dcd2ea2.html?stepindex2&st2&os0&bd_page_type1&net_type3 http://jingyan.baidu.com/article/20095761cbef40cb0721b417.html转载于:https://www.cnblogs.com/fyy-888/p/5272862.html
CSS动画无限循环
实现代码 div{animation:myanimation 5s infinite; }keyframes myanimation {from {top:0px;}to {top:200px;} } 注:animation ->Css3动画属性 myanimation->随便命名 infinite 可重复 ,去掉就不重复了 top可以改为宽高,或者方向等等任何CSS属性 form 开始 to结束…
apple id无法创建_我如何为我的Apple收藏夹创建网站
apple id无法创建A while ago I started an Apple collection. Ive been following Apple hardware (and its aesthetics) since I was a teenager, but at that time I didnt the have money to own a Mac. 前一段时间，我开始了一个苹果系列。 从我十几岁起我就一直…
bzoj1562[NOI2009]变换序列——2016——3——12
任意门：http://www.lydsy.com/JudgeOnline/problem.php?id1562 题目： 对于0,1,…,N-1的N个整数，给定一个距离序列D0,D1,…,DN-1，定义一个变换序列T0,T1,…,TN-1使得每个i,Ti的环上距离等于Di。一个合法的变换序列应是0,1,…,N-1的…
把view或者div绘制 canvas ，导出图片功能实现完整源码附效果图（兼容H5和小程序）
先看下效果图：（上面灰色块内的用div和CSS写出来的，然后绘制到canvas） 实现此功能需要使用到一个微信小程序的插件，插件官方文档地址： wxml-to-canvas | 微信开放文档 本博客代码环境，uniapp&a…
C 语言中的 switch 语句 case 后面是否需要加大括号
事件原由为编辑器的自动缩进，当 case 换行后不自动缩进。 于是在在想可以可否在 case 后面再大括号，让其自动缩进。 查了资料，发现 case 是可以加大括号的，相当于代码块。 而且还有另外一个用途，可以代码块头部定义变量…
问题 c: 插入排序_插入排序：它是什么，以及它如何工作
问题 c: 插入排序Insertion sort is a simple sorting algorithm for a small number of elements.插入排序是一种针对少量元素的简单排序算法。 例： (Example:) In Insertion sort, you compare the key element with the previous elements. If the previous ele…
在Java连接hbase时出现的问题
问题1： java.net.ConnectException: Connection refused: no further information zookeeper.ClientCnxn: Session 0x0 for server null zookeeper未启动，或无法连接，从查看各节点zookeeper启动状态、端口占用、防火墙等方面查看原因。问题2&…
codeforces 8C. Looking for Order 状压dp
题目链接 给n个物品的坐标， 和一个包裹的位置， 包裹不能移动。 每次最多可以拿两个物品， 然后将它们放到包里， 求将所有物品放到包里所需走的最小路程。 直接状压dp就好了。 #include <iostream> #include <vector> #…
H5刷新当前页面
location.reload();
sql的外键约束和主键约束_SQL主键约束用示例解释
sql的外键约束和主键约束A primary key is a column or a set of columns that uniquely identifies each row in a table.主键是一列或一组列，它们唯一地标识表中的每一行。 It’s called a “constraint” because it causes the system to restrict the data al…
str.format() 格式化字符串函数
语法 它通过{}和:来代替%。 “映射”示例 通过位置 In [1]: {0},{1}.format(kzc,18) Out[1]: kzc,18 In [2]: {},{}.format(kzc,18) Out[2]: kzc,18 In [3]: {1},{0},{1}.format(kzc,18) Out[3]: 18,kzc,18字符串的format函数可以接受不限个参数，位置可以…
css学习任务二：切图写代码
今天的任务是根据UI给的图进行切图，然后写出相应的页面，UI如下： 收获：学习前端知识一年有余，却因为老是找不到实战项目而得不到实际的提高，直到今天的学习我才知道切图是怎么一回事，明白了你看到…
Vue mixins（混入） 附代码示例详解
mixins 我们称它为 “混入” ； 官方的解释： 混入 (mixin) 提供了一种非常灵活的方式，来分发 Vue 组件中的可复用功能。一个混入对象可以包含任意组件选项。当组件使用混入对象时，所有混入对象的选项将被“混合”进入该组件本身的…
软件开发面试_如何为成功的软件开发工作面试做准备
软件开发面试Job interviews are stressful for many people. Besides the pressure of getting hired, you have to answer various questions before and during the interview – like what to wear, how to get prepared, how much money to ask for, and much more.求职面…
bzoj1070————2016——3——14
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id1070； 题目概括： Description 同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现…
CSS兼容性汇总
http://www.jb51.net/css/469020.html CSS属性Hack 把属性hack分为 前缀属性hack和 后缀属性hack CSS属性Hack（前缀）针对的浏览器_color:red;IE6及其以下的版本*color:red ;或者 color:red;IE7及其以下的版本CSS属性Hack（后缀）针对…
Vue 过渡组件，可实现组件或者页面的动画过渡或者css过渡
使用过渡效果，可以优化用户体验，Vue给我们封装了一个很好用的组件，专门用来处理过渡效果，下面我们来看看怎么使用它； Vue 提供了 transition 的封装组件，在下列情形中，可以给任何元素和组件添加…
解释型和编译型编程语言_解释型和编译型编程语言：有什么区别？
解释型和编译型编程语言Every program is a set of instructions, whether it’s to add two numbers or send a request over the internet. Compilers and interpreters take human-readable code and convert it to computer-readable machine code. 每个程序都是一组指令&a…
Beta 冲刺 （1/7）
队名：天机组 组员1友林 228（组长） 今日完成：查找了相关资料及api文档。明天计划：继续相关资料及源码。剩余任务：优化网络通讯机制主要困难：查找的代码调试较为困难。收获及疑问：暂无…
Vue全局路由侦听beforeEach路由守卫附代码使用示例
使用路由守卫beforeEach，可以实现路由侦听； 全局侦听路由跳转的实现代码： app.vue onLaunch: function(e) {this.$router.beforeEach((to, from, next) > {console.log($router,to,from);next();}); } to 是跳转路由之后的page对象&am…
Debug模式下加载文件，运行程序异常的慢
今天在进行单元测试的时候，debug模式下加载速度很慢，但是run模式下速度很快。 原因：在debug模式下，断点位置不当，解决办法 移除编译器中的所有断点。转载于:https://www.cnblogs.com/nww57/p/5277113.html
如何在Python中对字符串进行子字符串化
Python offers many ways to substring a string. It is often called ‘slicing’.Python提供了许多对字符串进行子字符串化的方法。 它通常被称为“切片”。 It follows this template:它遵循以下模板： string[start: end: step]Where,哪里， start:…
HttpPost导包遇到的问题
直接在当前项目 build.gradle文件修改如下 android { useLibrary org.apache.http.legacy compileSdkVersion 24 buildToolsVersion "24.0.0" defaultConfig { applicationId "com.ican.subjects" minSdkVe…
真相也许是这样
这两天同学们陆续上传了自己编写的小程序，等老师审查给成绩的时候才发现一部分同学是负分。原因就是他们有抄袭之嫌。恰巧我当时就在一位得了负分的同学旁边，他一脸郁闷的对我说”没道理啊，这是我自己编的啊“。这个我知道，的确是…