willcool4ever • 取出无序数组第K大个数（借助快速排序一次划分）

#include <iostream>

using namespace std;

void printArray(int *arr, int size)
{
    for(int i=0; i<size; ++i)
    {
        cout<< arr[i]<< ' ';
    }
    cout<<endl;
}

int partition(int array[], int high, int low)
{
    int pivot = array[high];

    while (low < high) {
        while (low < high && array[low] <= pivot ) {
            low++;
        }
        array[high] = array[low];

        // printArray(array, 7);
        while (low < high && array[high] >= pivot ) {
            high--;
        }

        array[low] = array[high];

        // printArray(array, 7);
    }

    array[low] = pivot;
    // cout<<"pos:"<<low<<endl;
    return low;
}

int selectK(int array[], int high, int low, int K)
{
    int pos = partition(array, high, low);

    if (K == pos - low + 1)
    {
       return array[pos];
    }else if(K > pos - low + 1)
    {
        return selectK(array, high, pos+1, K-(pos-low+1));
    }else{
        return selectK(array, pos-1, low, K);
    }

}

int main()
{
    int array[7] = {10, -22, 211, 120, -2, 23, 120};
    int size = sizeof (array) / sizeof (*array);

    printArray(array, size);

    cout<<"number:"<<selectK(array, size-1, 0, 4)<<endl;

    return 0;
}