快排分区函数

思路

并未真正的实现快速排序算法，只是找到了选中的数在数组中的顺序位置。

基本思想

选择一个数，把数组的数分为两部分，把比选中的数小或者相等的数移到数组的左边，把比选中的数大的数移动到数组的右边，返回分区后的选中数所在的下标。

对于获取数组中的前k个数，数组调用了分区函数之后：

1. 如果返回的下标是k-1，那么数组左边的k个数(数组下标从0到k-1)，就是k个最小的数；
2. 如果返回的下标大于k，那么从下标之前的数组中再次调用查找；
3. 如果返回的下标小于k，那么从下标开始之后的数组中再次调用查找。

效率

时间复杂度: o(n)
空间复杂度: o(1)

应用

1. 一维数组的最小(或大)的k个数；
2. 离直角坐标系原点最近的k个数；
3. 广泛运用在排序和海量数据挑选当中。

代码实现

// 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;
}