上次咱说了当数组里没有任何排序，quick select是一种普遍适用的搜索算法。

quick select算法咱们之前思路说过，每次找一个pivot，把比pivot小的放他左边，大的在右边。有了这个局部排序之后，就可以继续使用之前二分法算法的思路，当target > pivot, 就在pivot右边继续搜索。不然就在pivot左侧继续搜索。这个二分法搜索的思路之前说过，算法也介绍过，就不再赘述。

那具体我们怎么选择这个pivot并且进行排序呢？下面就是这个部分的算法。手机上手打，难免错漏，请见谅。

int getPivot(int left, int right, int[] nums){

int pivotIndex = (left + right)/2; // this can a random number between left and right

int pivot = nums[pivotIndex];

int curSlot = left; // 当前位置，把比pivot小的数换到这个位置上

swap(nums, pivotIndex, right); // 先把pivot丢到最后变不管它

// loop里把所有比pivot小的放到左边

for(int i =0; i < right; i++){

if(nums[i] < pivot){

swap(nums, curSlot++, i); // 每次要移动curSlot

}

}

// 最后把pivot放到最后一个比他小的数的后面，这样能保证[left, curSlot-1] < pivot，[curSlot + 1, right] >= pivot.

swap(nums, curSlot, right);

return curSlot;

}

swap这个很简单：

void swap(int [] nums, int i, int j){

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

quick select其实也有更简洁的写法，这里为了理解方便，用的比较经典的实现办法。

这部分算法也可以用在quick sort里。这一段其实本来就是quicksort的算法的一部分。以后有机会咱们再说说quick sort算法。