面试题:寻找第k小的数。

找出数组中第k大/小的数.

这个题是常见题，但是一直都没有动手写过。今天实现了一下。顺道写了下快排。说是很简单的代码，写起来也不容易。

最好的算法是基于快排的，复杂度大概为n。道理不解释。代码如下：

/*
 * =====================================================================================
 *
 *       Filename:  quicksort.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/10/2012 01:09:51 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>


#include <unistd.h>

#define swap(a,b) a^=b;b^=a;a^=b;

int* sort1round(int * nums, int size){
    printf ( "start sort!! %d\n",size );
    if(size<=1) return nums;
    int *tail = nums+size-1;
    int *head = nums;
    printf ( "key = %d\n", *head );
    while(1){
        while(*tail > *head && tail!=head)tail--;
        if(tail == head) break;
        if(*tail<=*head){
            //swap tail and key
            printf ( "1. swap %d %d\n", *tail, *head );
            swap(*tail, *head);
            head++;
            //now tail is the key
        }
        while(*tail > *head) head++;
        if(tail == head) break;
        if(*tail<*head && tail!=head){
            printf ( "2. swap %d %d\n", *tail, *head );
            swap(*tail, *head);
            tail--;
        }
    }
    printf ( "end sort with key = %d\n", *head );
    return head;
}

void quicksort(int *nums, int size){
    if(size<=1)return;
    int *key = sort1round(nums,size);
    quicksort(nums,key-nums);
    quicksort(key+1,nums+size-1-key);
}
int getk(int *nums,int size, int k){
    if(size<=1) return *nums;
    int *key = sort1round(nums,size);
    if(key-nums == k-1){
        return *key;
    }

    if(key-nums > k-1){
        return getk(nums,key-nums,k);
    }
    if(key-nums < k-1){
        return getk(key+1, nums+size-key-1, k - (key-nums+1));
    }
    return -1000;
}


/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {2,3,6,-2,4,5};
//    quicksort(input, sizeof(input)/4);
    int i;
    for(i=0;i<sizeof(input)/4;i++){
        printf ( "%d\n", input[i] );
    }
    printf ( "get k = 4 %d\n", getk(input, sizeof(input)/4,2 ));
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */