2019-05-23排序案例3

package 排序案例;

public class FindK {
    // 这个题的题意是给你一个乱序的数组让你在其中找出排好序的数组的某个位置的元素
    // 解法 1.在这个数组中随机partation得到一个数求出它在这个数组中的位置然后与
    // 要求的位置想比对如果相同就直接返回partation的那个下标的那个数如果大于的话
    // 就到这个partation数的左边去找小于就到右边找
    public static int partation(int[] arr, int l, int r) {
        int less = l - 1; // 边界必须从 -1 length开始因为你不知道第一个元素和最后一个元素是否小于target或者大于target
        int more = r + 1;
        int targt = arr[r];
        while(l < more) {
            if(arr[l] < targt) {
                swap(arr, ++less, l++);
            }else if(arr[l] == targt){
                l++;
            }else {
                swap(arr, l, --more);
            }
        }
        return more - 1;
    }
    public static int findK(int[] arr, int l, int r, int k) {
        // 这个函数的作用是找出在乱序的数组中找出排序后数组中k位置的元素k指的是位置而不是下标
        int p = partation(arr, l, r); // 
        int pw = p - l + 1; // pw指的是是p的位置
        if(pw == k) {
            return arr[p];
        }else if(pw > k) {
            return findK(arr, l, p - 1, k);
        }else {
            return findK(arr, p + 1, r, k - pw); 
            // 这里的k写成k-pw的原因是k在这里代表的是位置当pw<k说明这个元素在主元的后面接下来又开始进行递归
            // 因为k始终代表的就是那个目标数的位置下一次递归开始的时候理所应当的需要改变这也是为什么
            // 这也是为什么pw=p-l+1因为主元的是是随l，r的变化而变化的每一次递归都会变化
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 4, -1, 2};
        System.out.println(findK(arr, 0, arr.length - 1, 2));
        partation(arr, 0, arr.length - 1);
    }
}