关于获取某个序列中第k大元素的算法,很直观的想法是对序列进行排序,然后直接取下标为k - 1的元素的值即可,但是此种算法会有大量的冗余排序计算。本示例是基于快速排序算法演变而来的一种快速选择算法。我们知道在快速排序算法中每次递归都需要选择一个枢纽元,一般该枢纽元是选择为要排序的序列的中间元素,这里经过一次快速排序,枢纽元左边的元素都是小于枢纽元的,右边的元素都是大于枢纽元的,此时如果k - 1小于枢纽元的下标,那么再只需要对枢纽元左边的元素进行递归;如果k - 1大于枢纽元的下标,那么只需要对枢纽元右边的元素进行递归;如果k - 1等于枢纽元的下标,那么枢纽元即为要求的值;如此反复。需要说明的是,如果在某个时刻,要递归的序列的长度小于一定值(这里取20),那么使用递归的快速排序没有直接使用插入排序快,因而,这里在小序列部分采用了插入排序算法,最终要求的值直接在已排序的序列中获取即可。
- public class QuickSelect {
- public static <AnyType extends Comparable<? super AnyType>> AnyType quickSelect(AnyType[] arr, int k) {
- return quickSelect(arr, 0, arr.length - 1, k);
- }
- private static <AnyType extends Comparable<? super AnyType>> AnyType quickSelect(AnyType[] arr, int left, int right, int k) {
- if (left + CUT_OFF <= right) {
- AnyType pivot = medium(arr, left, right);
- int i = left, j = right;
- while (true) {
- while (arr[++i].compareTo(pivot) < 0) ;
- while (arr[--j].compareTo(pivot) > 0) ;
- if (i < j) {
- swapReferences(arr, i, j);
- } else {
- break;
- }
- }
- swapReferences(arr, i, right);
- if (k <= i) {
- return quickSelect(arr, left, i - 1, k);
- } else if (k > i + 1) {
- return quickSelect(arr, i + 1, right, k);
- } else {
- return arr[i + 1];
- }
- } else {
- insertionSort(arr, left, right);
- return arr[k - 1];
- }
- }
- private static <AnyType extends Comparable<? super AnyType>> AnyType medium(AnyType[] arr, int left,
- int right) {
- int center = (left + right) / 2;
- if (arr[center].compareTo(arr[left]) < 0) {
- swapReferences(arr, center, left);
- }
- if (arr[left].compareTo(arr[right]) > 0) {
- swapReferences(arr, left, right);
- }
- if (arr[center].compareTo(arr[right]) < 0) {
- swapReferences(arr, center, right);
- }
- return arr[right];
- }
- private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] arr, int i, int j) {
- AnyType tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- private static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a, int left, int right) {
- int j;
- for (int p = left; p <= right; p++) {
- AnyType tmp = a[p];
- for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
- a[j] = a[j - 1];
- }
- a[j] = tmp;
- }
- }
- private static final int CUT_OFF = 20;
- }
来源: https://www.oschina.net/code/snippet_2831721_58540