#include <IOStream>
#include <cstdlib>
using namespace std;
#define SIZE 20
#define myrand() rand() % SIZE
void bubble(int a[], int start, int end){
for(int i = 0; i <= end-start; i++){
for(int j = start; j < end - i; j++){
if(a[j] > a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
int partition(int a[], int start, int end, int x){
for(;start < end; start++){
if(a[start] > x){
while(start < end && a[end] > x)
end--;
if(start != end){
int tmp = a[end];
a[end] = a[start];
a[start] = tmp;
}else
break; //这里一定要加这条语句，否则外部循环start会在+1
}
}
return start - 1;
}
int select(int a[], int start, int end, int k){
int i, s, t;
if(end - start < 5){
bubble(a,start,end);
return a[start+k-1];
}
for(i = 0; i < (end-start+1)/5; i++){
s = start + 5*i;
t = s + 4;
bubble(a,s,t);
int tmp = a[start+i];
a[start+i] = a[s+2];
a[s+2] = tmp;
}
if((end-start+1) % 5 != 0){
s = start + 5*i;
bubble(a,s,end);
int tmp = a[start+i];
a[start+i] = a[(s+end)/2];
a[(s+end)/2] = tmp;
i++;
}
i--;
int x = select(a,start, start+i, (i+1)/2);
i = partition(a,start, end, x);
int j = i - start + 1;
//这里之所以没有加入j == k的判断是因为在partiton时无法将x排在正确的位置使得左边都小于x而右边都大于x只能保证一边>,另一边<=;
if(j >= k)
return select(a, start, i, k);
else
return select(a, i+1, end, k-j);
}
int main(){
clock_t start, end;
srand((int)time(NULL));
int a[SIZE];
int n = 5;

 for(int i = 0; i < SIZE; i++){
a[i] = myrand();
cout << a[i] << " ";
if((i+1)%5 == 0)
cout << endl;
}
start = clock();
cout << "the no " << n << " is: " << select(a, 0, SIZE-1, n) << endl;
end = clock();
cout << "Time: " << (double)(end - start) << endl;
return 0;
}