#include <stdio.h>
#include <stdlib.h>
int FindMinK(int data[], int l, int r, int k)
{
    int m = data[l+k-1], t = 0;
    int i, j;
    data[l+k-1] = data[r], data[r] = m;
    for (i = l-1, j = l; j != r; ++j)
        if (data[j]<m)
            t=data[++i], data[i]=data[j], data[j]=t;
    t=data[++i], data[i]=data[j], data[j]=t;
    if (k==i-l+1) return m;
    if (k>i-l+1) return FindMinK(data, i+1, r, k-i+l-1);
    else    return FindMinK(data, l, i-1, k);
}
int main()
{
    int data[]={8,6,6,4,4,3,2,1};
    for (int i = 1; i <= sizeof(data)/sizeof(data[0]); ++i)
        printf("%d\n", FindMinK(data, 0, 7, i));
    return 0;
}

template<typename _RandomAccessIterator>
    void
    nth_element(_RandomAccessIterator __first,
        _RandomAccessIterator __nth,
        _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

      while (__last - __first > 3)
    {
      _RandomAccessIterator __cut =
        std::__unguarded_partition(__first, __last,
                       _ValueType(std::__median(*__first,
                                *(__first
                                  + (__last
                                     - __first)
                                  / 2),
                                *(__last
                                  - 1))));
      if (__cut <= __nth)
        __first = __cut;
      else
        __last = __cut;
    }
      std::__insertion_sort(__first, __last);
    }
    
    template<typename _RandomAccessIterator>
    void
    __insertion_sort(_RandomAccessIterator __first,
             _RandomAccessIterator __last)
    {
      if (__first == __last)
    return;

      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    {
      typename iterator_traits<_RandomAccessIterator>::value_type
        __val = *__i;
      if (__val < *__first)
        {
          std::copy_backward(__first, __i, __i + 1);
          *__first = __val;
        }
      else
        std::__unguarded_linear_insert(__i, __val);
    }
    }

#include <stdio.h> 
#include <stdlib.h> 
#define MAXSIZE 100 

typedef int datatype; 
typedef struct 
{ 
    datatype data[MAXSIZE]; 
    int last; 
}SeqList; 

SeqList *CreatSeqList() 
{ 
    SeqList *L; 
    int temp,i=0; 
    L=(SeqList *)malloc(sizeof(SeqList)); 
    L->last=-1; 
    printf("please input the numbers:(End with any character)\n"); 
    while(scanf("%d",&temp)) 
        L->data[i++]=temp; 
    --i; 
    L->last=i; 
    return L; 
} 

datatype part(SeqList *L,int a,int b,int k) 
{ 
    int i,j; 
    datatype m,t; 
    datatype* data = L->data;
    m=data[a+k-1], data[a+k-1] = data[b],data[b] = m; 
    for (i=a-1, j = a; j != b; ++j)
        if (data[j] < m)
            t=data[++i], data[i]=data[j], data[j]=t;
    t=data[++i], data[i]=data[j], data[j]=t;
    if (k==i-a+1) return m;
    if (k>i-a+1) return part(L, i+1, b, k-i+a-1);
    else        return part(L, a, i-1, k);
} 


int    main() 
{ 
    SeqList *L; 
    datatype x; 
    int k,n; 
    L=CreatSeqList(); 
    n=L->last; 
    printf("The total number is %d\n",n+1); 
    printf("Now you can enter number k(1 <=k <=%d):\n",n+1); 
    fflush(stdin);
    scanf("%d",&k); 
    x=part(L,0,L->last,k); 
    printf("The %d smallest is %d",k,x); 
//    getch(); 
    return 0;
}
please input the numbers:(End with any character)
1 3 4  5 7 9
b
The total number is 6
Now you can enter number k(1 <=k <=6):
3
The 3 smallest is 4Press any key to continue