2018-01-20 计算数组中 第K大的数

• 使用快速排序的思想进行实现

每次排序,会确定一个基准点,从大到小排序的话,基准点左边的数,都比基准点大,基准点右边的数,都比基准点小. 第一次确定基准点后,与 K 进行比较,如果k-1 == 基准点的位置(k减一是因为数组下标是从0开始的,第一大,就是 0 位,第二大,就是1 位), 那么,基准点的数字就是第K大的数, 否则, 如果k - 1 大于基准点,说明第K大的数,在右边的区间中, 否则说明在左边的区间中,然后继续递归,直到找到基准点.

//计算基准点
int calculate(int *q,int low,int high) {

    int tmp = q[low];

    while (low < high) {
        while (low < high && q[high] <= tmp) {
            high--;
        }
        q[low] = q[high];

        while (low < high && q[low] > tmp) {
            low++;
        }
        q[high] = q[low];
    }
    q[low] = tmp;
    return low;
}

int find(int *q,int k ,int low,int high){
    int position = calculate(q,low,high);
    if( position == k - 1){
        return position;
    }
    if(position > k - 1){
        return find(q,k,low,position - 1);
    }else {
        return find(q,k,position + 1,high);
    }
}
//快速排序
void  sort(int *q,int low,int high){
    if(low < high){
        int position = calculate(q,low,high);
        sort(q,low,position-1);
        sort(q,position+1,high);
    }
}


int kthlargest(){
    
    //数组
    int quen[] = {4,3,6,1,5,3,7,9};
    //数组长度
    int len = sizeof(quen)/sizeof(int);

    printf("排序前:\n ");
    for(int i = 0;i < len ;i++){
        printf(" %d ",quen[i]);
    }
    printf("\n");
    int k = 4;
    int position = find(quen,k,0,len - 1);
    printf("---第%d大的数是--%d---\n",k,quen[position]);
    printf("排序后:\n");
    sort(quen,0,len-1);

    for(int i = 0;i < len ;i++){
        printf("%d ",quen[i]);
    }
    printf("\n");
}