分治法/第k小的元素

更改了快速排序的QuickSort方法
快速排序参考网址

package xcrj.kchalgorithm.divideConquer;

/**
 * 寻找序列中第k小元素
 * 利用快速排序
 * 快速排序：子序列左右比较定轴值索引，这个轴值索引就是第k-1小的
 * - 树形分区排序
 * - 递归分区内比较交换返回轴值索引
 * - 递归（根据轴值索引）进行左右分区划分》分区内左右索引对应值比较交换，索引相等时返回轴值索引
 * - 轴值左分区数值< 轴值 <轴值右分区数值
 */
public class KthMin {

    /**
     * 寻找序列中第k小元素
     *
     * @param r     输入数组
     * @param start 分区左边界
     * @param end   分区右边界 r.length-1
     * @param k     第k小的元素位于k-1索引处
     */
    public static int kthMin(int[] r, int start, int end, int k) {
        int pivot;
        if (start < end) {
            // 分区内比较交换获取轴值索引
            pivot = partition(r, start, end);
            if (pivot == k - 1) {
                return r[k - 1];
            }
            if (pivot > k - 1) {
                // 递归左分区
                return kthMin(r, start, pivot - 1, k);
            } else {
                // 递归右分区
                return kthMin(r, pivot + 1, end, k);
            }
        }

        if (start == end && start == k - 1) {
            return r[k - 1];
        }

        return -1;
    }

    /**
     * 分区内比较交换返回轴值索引
     *
     * @param start 分区左边界
     * @param end   分区右边界
     * @return 轴值索引
     */
    public static int partition(int[] r, int start, int end) {
        int left = start;
        int right = end;
        // 临时交换变量
        int temp;
        // 保证left<right
        while (left < right) {
            while (left < right && r[left] < r[right]) right--;
            if (left < right) {
                temp = r[right];
                r[right] = r[left];
                r[left] = temp;
                // r[left]和r[right]比较过了，不再比较
                left++;
            }
            while (left < right && r[left] < r[right]) left++;
            if (left < right) {
                temp = r[right];
                r[right] = r[left];
                r[left] = temp;
                // r[left]和r[right]比较过了，不再比较
                right--;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] inputs = {1, 2, 3, 10, 20, 20};
        int result = kthMin(inputs, 0, inputs.length - 1, 5);
        System.out.println(result);
    }
}

最后

以上就是开心人生为你收集整理的分治法/第k小的元素的全部内容，希望文章能够帮你解决分治法/第k小的元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。