求数组中第n大（小）的元素

1 算法原理

使用快速排序进行查找，类似于二分查找的意思，因为每次都会有一个元素找到适当位置，该位置就是这个元素在数组中的排列顺序。每次partition会返回一个数组下标，将该数组下标的元素和待查找的值进行比较，如果相等，直接返回，如果大于，取partition操作后的右一侧，反之，取左一侧。

2 时间复杂度

利用快速排序进行查找，类似与二分查找思想，其操作数为 n+n/2+n/4+.....，由此可见，其时间复杂度为O(n)

3 实现

/** * 求数组中第k小的元素 * 快速排序 * 时间复杂度为O(n) * @author xld * */ public class Selection { public static int solve(int[] arr, int k) { return solve(arr, 0, arr.length - 1, k); } public static int solve(int[] arr, int l, int r, int k) { if (arr[l] == k) return arr[l]; int p = partition(arr, l, r); if (arr[p] == k) return arr[p]; else if (arr[p] > k) return solve(arr, l, p - 1, k); else return solve(arr, p + 1, r, k); } public static int partition(int[] arr, int l, int r) { int v = arr[l]; int j = l; for (int i = l + 1; i <= r; i++) { if (arr[i] < v) { j++; swap(arr, i, j); } } swap(arr, l, j); return j; } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // 测试InsertionSort public static void main(String[] args) { int[] arr = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; int ret = Selection.solve(arr, 3); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); System.out.print(' '); } System.out.println(); System.out.println("第k小的元素为："+ret); } }