求第k小的元素

用快排解决：

用快排，一趟排序后，根据基准值来缩小问题规模。基准值的下角标i 加1 表示了基准值在数组中第几小。如果k<i+1,那就在左半边找；如果k>i+1那就在右半边找。当基准值的下角标+1=k，那就找到答案了。

public class FindTopKth { private FindTopKth() {} /**  * @param arr 待查找的数组  * @param left 待查找数组的左边界  * @param right 待查找数组的右边界  * @param k  查找第k小的元素  * @param <T> 泛型  * @return 返回第k小的元素  */ public static <T extends Comparable<? super T>> T find(T[] arr, int left, int right, int k) {  int p = partition(arr, left, right, k);  if (p == k) {   return arr[p];  } else if (k < p) {   return find(arr, left, p - 1, k);  } else {   return find(arr, p + 1, right, k);  } } private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right, int k) {  T base = arr[left];  int j = left;  for (int i = left+1; i <= right; i++) {   if (arr[i].compareTo(base) < 0) {    swap(arr, i, ++j);   }  }  swap(arr, left, j);  return j; } private static void swap(Object[] arr, int i, int j) {  if (i != j) {   Object temp = arr[i];   arr[i] = arr[j];   arr[j] = temp;  } } public static <T extends Comparable<? super T>> T find(T[] arr, int k) {  return find(arr,0,arr.length-1,k-1); } public static void main(String[] args) {  Integer[] arr = {3, 1, 9, 7, 5, 11};  System.out.println(find(arr,1));//第1小的 //1  System.out.println(find(arr,2));//第2小的 //3  System.out.println(find(arr,3));//第3小的 //5  System.out.println(find(arr,4));//第4小的 //7  System.out.println(find(arr,5));//第5小的 //9  System.out.println(find(arr,6));//第6小的 //11 }}

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：求第k小的元素

关键词：