//下面两种part效率比较：相同运算量下part比part2快5倍左右，part2写法简单但是效率低 #include "stdafx.h"
#include <iostream>
#include <stdio.h>
using namespace std; int part(int *arr, int l , int r)
{
c_num += r - l;
swap(arr[r],arr[l+rand()%(r-l)]);
int q = r--;
while( l < r)
{
while(l <= r && arr[l] <= arr[q]) ++l;
while(l < r && arr[r] >= arr[q]) --r;
if(l<r&&arr[l]>arr[r]) swap(arr[l], arr[r]);
}
if(l<q&&arr[l]>arr[q]) swap(arr[l], arr[q]);
return l;
} int part2(int *arr, int l , int r)
{
c_num += r - l;
int k, q = l;
swap(arr[l], arr[l+rand()%(r-l)]);
for(k = l+; k <= r; ++k)
{
if(arr[k] <= arr[q])
{
if(++l != k)
swap(arr[l], arr[k]);
}
}
swap(arr[l], arr[q]);
return l;
} void qsort(int *arr, int l, int r)
{
if(l >= r) return;
int mid = part(arr, l , r);
qsort(arr, l, mid-);
qsort(arr,mid+, r);
} int findNumK(int *arr, int l, int r, const int k)
{
if(l >= r)
{
return arr[k];
}
int mid = part(arr, l , r);
if(k < mid)
{
return findNumK(arr, l, mid-, k);
}
else if (k > mid)
{
return findNumK(arr,mid+, r, k);
}
else
{
return arr[k];
}
}
#define MAX_RAND 82934829
int myRand(int n)
{
return (long((double)rand()/RAND_MAX * MAX_RAND))%n;
}
const int n = ;
int ki = ;
int arr[n];
int brr[n];
int _tmain(int argc, _TCHAR* argv[])
{
for(int i = ; i < n; ++i)
{
arr[i] = i;
}
for(int i = ; i < n; ++i)
{
swap(arr[i],arr[myRand(n)]);
}
for(int i = ; i < n; ++i)
{
brr[i] = arr[i];
}
printf("@@@@@@@\n");
while(cin>>ki)
{
printf("\n%d %d\n", c_num, findNumK(brr, , n-, n-ki));
for(int i = ; i < n; ++i)
{
brr[i] = arr[i];
}
c_num = ;
}
printf("\n################\n");
c_num = ;
qsort(arr, , n-);
for(int i = n-; i >= n - ki; --i)
{
printf("%d ", arr[i]);
}
printf("\n%d\n",c_num);
getchar();
return ;
}