快排分区函数
思路
并未真正的实现快速排序算法，只是找到了选中的数在数组中的顺序位置。
基本思想
选择一个数，把数组的数分为两部分，把比选中的数小或者相等的数移到数组的左边，把比选中的数大的数移动到数组的右边，返回分区后的选中数所在的下标。
对于获取数组中的前k个数，数组调用了分区函数之后：
- 如果返回的下标是k-1，那么数组左边的k个数(数组下标从0到k-1)，就是k个最小的数；
- 如果返回的下标大于k，那么从下标之前的数组中再次调用查找；
- 如果返回的下标小于k，那么从下标开始之后的数组中再次调用查找。
效率
时间复杂度: o(n)
空间复杂度: o(1)
应用
- 一维数组的最小(或大)的k个数；
- 离直角坐标系原点最近的k个数；
- 广泛运用在排序和海量数据挑选当中。
代码实现
// C++
void Swap(int &first_number, int &second_number) {
int temp = first_number;
first_number = second_number;
second_number = temp;
}
int Partition(int array[], int start, int end, int pivot_index) {
int pivot = array[pivot_index];
int store_index = start;
Swap(array[pivot_index], array[end]);
for (int iLoop = start; iLoop < end; iLoop++) {
if (array[iLoop] < pivot) {
Swap(array[iLoop], array[store_index]);
store_index++;
}
}
Swap(array[store_index], array[end]);
return store_index;
}
