题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度分析:blablabla
C++ 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int q[] = new int[n];
for (int i = 0; i < n; i++) q[i] = scanner.nextInt();
System.out.println(quickSort(q, 0, n - 1, k - 1));
// for (int i = 0; i < n; i ++ ) System.out.printf("%d ", q[i]);
}
private static int quickSort(int[] arr, int low, int high, int k) {
if (low < high) {
int middle = getMiddle(arr, low, high);
if (middle > k)
return quickSort(arr, low, middle - 1, k);
else if (middle == k) {
return arr[middle];
} else
return quickSort(arr, middle + 1, high, k);
}
// System.out.println(low+" "+high);
return arr[low];
}
private static int getMiddle(int[] arr, int low, int high) {
int temp = arr[low];
while (low < high) {
while (low < high && arr[high] >= temp) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= temp) {
low++;
}
arr[high] = arr[low];
}
arr[high] = temp;
return high;
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}