Quick Select Algorithm 快速选择算法

更多代码和Leetcode题目解析请看这里

什么是Quick select?

• Quick select算法通常用来在未排序的数组中寻找第k小/第k大的元素。其方法类似于Quick sort。Quick select和Quick sort都是由Tony Hoare发明的，因此Quick select算法也被称为是Hoare's selection algorithm。
• Quick select算法因其高效和良好的average case时间复杂度而被广为应用。Quick select的average case时间复杂度为O(n)，然而其worst case时间复杂度为O(n^2)。
• 总体而言，Quick select采用和Quick sort类似的步骤。首先选定一个pivot，然后根据每个数字与该pivot的大小关系将整个数组分为两部分。那么与Quick sort不同的是，Quick select只考虑所寻找的目标所在的那一部分子数组，而非像Quick sort一样分别再对两边进行分割。正是因为如此，Quick select将平均时间复杂度从O(nlogn)降到了O(n)。

Quick select算法描述

Input: array nums, int k. (find kth smallest element in an unsorted array)
Output: int target

1. Choose an element from the array as pivot, exchange the position of pivot and number at the end of the array.
   
   • The