import java.util.Scanner;
/**
* 利用快排中parition算法柴信，找到第k大數(shù)，平均時間復(fù)雜度為O(n)
*/
public class FindK
{
//測試
public static void main(String[] args)
{
int k = 0;
Scanner scanner = new Scanner(System.in);
k = scanner.nextInt();
scanner.close();
int[] a = {2, 6, 3, 10, 45, 12, 5, 6, 5, 6};
if (k >= 0 && k < a.length) {
findMaxK(a, 0, a.length - 1, k);
System.out.println("第"+ (k+1) +"大數(shù)為：" + a[k]);
} else
System.out.println("are you kidding me ?");
}
//遞歸劃分
private static void findMaxK(int[] a, int low, int high, int k)
{
int p = partition(a, low, high);
if (p == k)
{
return;
}
if (p < k)
{
findMaxK(a, p + 1, high, k);
}else{
findMaxK(a, low, p - 1, k);
}
}
//核心算法：劃分
private static int partition(int[] a, int low, int high)
{
int position = a[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (a[j] <= position)
{
++i;
exchange(a, i, j);
}
}
exchange(a, i + 1, high);
return i + 1;
}
static void exchange(int[] a, int i, int j)
{
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
