题解 | #NC88-寻找第K大#

/**
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
/*****************************************************
* 快速排序将数组从大到小排列，第K个最大元素下标为K-1
*****************************************************/
int partition(int *a, int left, int right)
{
    int i = left+1;
    int j = right;
    int tmp;
    int pivot = a[left];
    
    while(1)
    {
        while(i <= j && a[i] >= pivot) i++;
        while(i <= j && a[j] <= pivot) j--;
        if(i >= j)
            break;
        tmp  = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    a[left] = a[j];
    a[j] = pivot;
    return j;
}

int *quickSort(int *a, int left, int right)
{
    int mid;
    if(left < right)
    {
        mid = partition(a, left, right);
        
        a = quickSort(a, left, mid-1);
        a = quickSort(a, mid+1, right);
    }
    return a;
}


int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    
    quickSort(a, 0, aLen-1);
    return a[K-1];
}