寻找数组中最小的k个数。基于快排。keywords:快排，两种findp实现

findmink.c

/*
 * =========================================================
 *       Filename:  findmink.c
 *    Description:  基于快排的两种寻找pivot元素位置的方法
 *    来实现寻找数列中最小的k个数字
 *
 * =========================================================
 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SWAP(a,b) do{int temp;temp=a;a=b;b=temp;}while(0)
typedef struct interval{
    int left;
    int right;
}Interval;
int findp_v1(int a[] , int left , int right);
Interval *findp_v2(int a[] , int left , int right);
int findmink(int a[],int left,int right,int k);
void print(int a[],int start,int end);
int main(){
    long seed;
    seed=time(NULL);
    srand(seed);

    int *a , n , k ,kth;
    while(scanf("%d%d",&n ,&k) == 2){
        a = malloc(sizeof(int) * n);
        for(int i = 0; i < n ; ++i)
            scanf("%d",a + i);
        findmink(a , 0 , n-1 , k);
        print(a , 0 ,k- 1);
        free(a);
    }
}

int findmink(int a[],int left,int right,int k){
//    int p=k-1;
//    Interval *inter;
//    inter = findp_v2(a , left ,right);
//    if(p >= inter->left && p <= inter->right)
//        return k;
//    else if(p < inter->left)
//        return findmink(a , left ,inter->left -1 ,k);
//    else
//        return findmink(a , inter->right +1 ,right,k);
    int p = findp_v1(a , left ,right);
    if( p < k-1)
        return findmink(a , p+1 , right , k);
    else if(p > k-1)
        return findmink(a , left , p-1 ,k);
    else
        return k;
}


int findp_v1(int a[] , int left , int right){ // left <= pivot <= right
    //从[left , right]随机选出pivot元素 
    int random=rand()%(right-left+1)+left;
    SWAP(a[left],a[random]);
    int pivot=a[left];
    int l = left + 1;
    int r = right;
    while(l < r){// l == r 时跳出循环
        while(a[l] <= pivot && l < r)
            ++l;
        while(a[r] >= pivot && l < r)
            --r;
        if(l < r)
            SWAP(a[l] , a[r]);
    }
    if(a[l] >= pivot){
        SWAP(a[l-1] , a[left]);
        return l-1;
    }
    else{
        SWAP(a[l] , a[left]);
        return l;
    }
}

/*
以[0,n-1]为例解释各个参数的含义
[1,l]<p  l指向最后一个小于p的数
(r,n]>p  r+1指向第一个大于p的数
(l,i)=p
[i,r] 未处理的数
*/
Interval *findp_v2(int a[] , int left , int right){
    int random = rand() % (right - left + 1) + left;
    SWAP(a[left] , a[random]);
    int pivot = a[left];
    int l=left,r=right;
    int i;
    for(i=left+1;i<=r;i++){
        if(a[i]<pivot){
            l++;
            SWAP(a[l],a[i]);
        }
        else if(a[i]>pivot){
            while(a[r]>pivot && r>=i)// important!!!
                r--;
            if(r>=i){
                SWAP(a[r],a[i]);
                r--;
                if(a[i]<pivot){
                    l++;
                    SWAP(a[l],a[i]);
                }
            }
        }
    }
    SWAP(a[left],a[l]);
    Interval *inter = malloc(sizeof(Interval));
    inter->left = l;
    inter->right = r;
    return inter;
}
void print(int a[],int start,int end){
    int i;
    for(i=start;i<=end;i++)
        printf("%d%s",a[i],(i==end)?"\n":" ");
}