使用快排解题, 具体解题步骤看代码
快排的方法有很多种, 下面给出两种题解
方法一: y总的快排模板
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
// 对输入数据进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
// 求解的第 k小的数, 下标为 k -1
System.out.println(quickSort(arr, 0, n - 1, k - 1));
}
// 语义: 使用快速排序查找,返回下标为 index的元素值
private static int quickSort(int[] arr, int l, int r, int index) {
// 如果只剩下一个元素, 则说明为查找元素
if (l >= r) return arr[l];
// 快速排序进行查找
int p = arr[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (arr[i] < p);
do j--; while (arr[j] > p);
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 使用 j进行左右划分, 所以所查询下标和 j进行比较
if (j >= index) // 如果 j = index,下次的查询要包含下标 j
return quickSort(arr, l, j, index);
else
return quickSort(arr, j + 1, r, index);
}
}
方法二: 挖坑法进行快排
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 初始化输入数据
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
// 求第 k小的数, 下标为 k-1
System.out.println(quickSortSolution(arr, 0, n - 1, k - 1));
}
// 查找
private static int quickSort(int[] arr, int l, int r, int k) {
// 只剩下一个元素, 递归结束
if (l >= r) return arr[l];
// 求出基准值
int middle = getMiddle(arr, l, r);
if (middle > k) // 在左边继续进行查找
return quick(arr, l, middle - 1, k);
else if (middle == k) {
return arr[middle];
} else { // middle < k
return quickSort(arr, middle + 1, r, k);
}
}
// 对 [l...r]中的数据进行快排, 返回基准值的下标
private static int getMiddle(int[] arr, int l, int r) {
int p = arr[l]; // 对第一个数进行快排
while (l < r) {
while (l < r && arr[r] >= p) r--;
arr[l] = arr[r];
while (l < r && arr[l] <= p) l++;
arr[r] = arr[l];
}
arr[l] = p;
return l;
}
}
两种快排的区别
-
y总: 快排结束后 i 不一定 = j, 并且 基准值并不一定已经调整到自己的位置
-
挖坑法: 最后 l == r, 并且基准值已经调整到自己的位置上, i为基准值的下标
基于两者的不同, 所以解题思路上也略有不同
如果元素有相同的怎么办