AcWing 785. 快速排序 原题链接
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
private static void quickSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int base = arr[start];
int left = start - 1;
int right = end + 1;
while (left < right) {
while (arr[++left] < base);
while (arr[--right] > base);
if (left < right) MyOptions.swap(arr, left, right);
}
quickSort(arr, start, right);
quickSort(arr, right + 1, end);
}
AcWing 786. 第k个数 原题链接
给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第k小数。
数据范围
1≤n≤1000001≤n≤100000, 1≤k≤n1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3
private static int findKNumber(int[] arr, int k, int start, int end) {
if (start >= end) {
return arr[end];
}
int l = start - 1;
int r = end + 1;
int base = arr[start];
while (l < r) {
while (arr[++l] < base);
while (arr[--r] > base);
if (l < r)
MyOptions.swap(arr, l, r);
}
if (r >= k) {
return findKNumber(arr, k, start, r);
}else {
return findKNumber(arr, k, r + 1, end);
}
}