笨鸟先飞

1、快排递归解法：

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        //快排思路
        //找一个基数，大于基数的放左边，小于基数的放另右边
        //看基数的位置，如果基数的索引位置大于k说明k位于左边区间，否则位于右边区间
        //二分递归，直到 基数的位置等于k-1
        return quickSort(a,0,n-1,K-1); 
    }
    public int quickSort(int[] arr,int begin,int end,int k){
        //中轴线取左侧第一个元素
        int b = begin;
        int e = end;
        int pivot = arr[begin];
        while(begin<end){
            //找右边大于中轴线的元素
            while(begin<end&&arr[end]<=pivot){
                end--;
            }
            //右侧移到中轴线的左侧
            arr[begin] = arr[end];
            //找左侧小于中轴线的元素
            while(begin<end&&arr[begin]>=pivot){
                begin++;
            }
            //左侧移到中轴线的右侧
            arr[end] = arr[begin];
        }
        arr[begin] = pivot;

        if(begin==k){
            return arr[begin];
        }else if(begin>k){
            //k在左侧区间
            return quickSort(arr,b,begin-1,k);
        }else{
            //k 在右侧区间
            return quickSort(arr,begin+1,e,k);
        }   
    } 
}

2、快排非递归解法：

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        //快排思路 非递归解法
        //找一个基数，大于基数的放左边，小于基数的放另右边
        //看基数的位置，如果基数的索引位置大于k说明k位于左边区间，否则位于右边区间
        //重置begin和end的位置，继续循环，直到 中轴线位置 pivot==k-1
        return quickSort(a,0,n-1,K-1);   
    }

    public int quickSort(int[] arr,int begin,int end,int k){
        //中轴线取左侧第一个元素
        while(true){
            int b = begin;
            int e = end;
            int pivot = arr[begin];
            while(begin<end){
                //找右边大于中轴线的元素
                while(begin<end&&arr[end]<=pivot){
                    end--;
                }
                //右侧移到中轴线的左侧
                arr[begin] = arr[end];
                //找左侧小于中轴线的元素
                while(begin<end&&arr[begin]>=pivot){
                    begin++;
                }
                //左侧移到中轴线的右侧
                arr[end] = arr[begin];
            }
            arr[begin] = pivot;
            if(begin==k){
                break;
            }else if(begin>k){
                //k在左侧区间
                end = begin-1;
                begin = b;
                continue;
            }else{
                //k 在右侧区间
                begin = begin+1;
                end = e;
                continue;
            }
        }
        return arr[begin]; 
    }   
}