快速选择Java实现

快速选择算法

一、基本原理： 从一个数组中，快速找到一个排名第K大或者第K小的元素。

二、实现思路：依据快排的思路，找到轴枢元素的索引与排名k之间的关系。

三、具体分析：

举例1：

问题： 假如现在有6个学生的体重，想知道6个学生中体重第二轻的是多少kg？

抽象成如下问题：

在未排序的数组中，找到排名第K的元素。

给定一个数组： [30,83,56,76,21,95] 和 k = 2

输出： 30

结合之前学习过的快速排序，我们只需要保证轴枢元素（X）前的元素均比X小，X后的元素均比X大即可。且比X小的元素为k-1个，那么此时的X就是我们需要找的第K位元素。

即没必要对原数组进行整体的排序，只需要找到满足条件的元素X即可。

参照快速排序的partion过程，在第一轮结束后，轴枢元素X的位置为ind

import java.util.Arrays;

public class quick_sort_test {


    public static void main(String[] args) {
        int[] arr = new int[] {30,83,56,76,21,95};
        quickSort(arr, 0 ,arr.length-1);

        System.out.println(Arrays.toString(arr));
    }


    public void swap(int[] nums, int i, int j) {
        if(i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;

    }

    public static void quickSort(int[] nums, int left, int right) {
        int middle;
        if(left < right) {
            middle = partition(nums, left, right);
            System.out.println("轴枢元素的下标：" + middle);
            System.out.println("轴枢元素的值：" + nums[middle]);
//          对分界值分隔的两个数组，继续递归该方法。
//            quickSort(nums, left, middle-1);
//            quickSort(nums, middle+1, right);
        }

    }
    //执行完一次后，输出分界值的坐标
    public static int  partition(int[] nums, int left, int right) {
        if (left > right) {
            return 0;
        }

        int pivot = nums[left];

        while(left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }

            nums[right] = nums[left];

        }
        nums[left] = pivot;

        return left;
    }

}

将测试数组传入，轴枢的元素的下标ind为1（即为排名第k=2的元素）， X的值为30

问题中的k=2(当k=3, k = 1是分别得出以下结论：)

• 当 ind = k -1 时，此时的ind对应的元素X就是要求解的值。
• 当 ind < k -1 时，此时需要从轴枢元素分隔的后部分数组开始寻找，范围为：[ind+1, nums.length-1]
• 当 ind > k - 1时，测试需要从轴枢元素分隔的前部分数组开始寻找，范围为： [0， ind-1]

image-20220404121847456.png

落到具体的代码上：

import java.util.Arrays;

public class quick_select {
    public static void main(String[] args) {
        int[] arr = {30,83,56,76,21,95};

//      快速选择算法：从数组中找出排名第k位的元素，并输出。
//      eg: 从数据中找出排名第2的元素。
        int k = 2;
//      int k = 3;
//      int k = 1;

        int result = quickSelect(arr, 0, arr.length-1, k);

        System.out.println("排名第" +k +  "位的元素值为：" + result + "\n");

        System.out.println("此时数组的内容为：" + Arrays.toString(arr
        ));
    }

    public static void swap(int[] nums, int i, int j ) {
        if(i == j) {
            return;
        }

        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    /**
     * 快速排序的核心思想是找到排名第k位置的元素， 所以仅需保证前k-1的元素比k位置的元素小即可，
     * 没有必要对整个数组进行全部的排序
     * @param nums
     * @param left
     * @param right
     * @param k
     * @return  返回的是排名第K位置的元素值。
     */

    public static int quickSelect(int[] nums, int left, int right, int k) {
        if(left > right) {
            return 0;
        }

        while (left < right) {
            int privot = nums[left];

            while (left < right && nums[right] >= privot) {
                right--;
            }

            nums[left] = nums[right];

            while (left < right && nums[left] <= privot) {
                left++;
            }

            nums[right] = privot;
        }

//      完成了第一轮比较，此时left和right相等，均指向第一个轴枢元素。即ind = left = right
        int ind = left;
        if(ind == k - 1) {
            return nums[ind];
        } else if (ind < k - 1) {
            return quickSelect(nums, ind + 1, nums.length-1, k);
        } else {
            return  quickSelect(nums, 0, ind-1, k);
        }
    }



}

①、当k = 2（ind == k - 1），执行结果如下：

ind == k - 1

②、当k = 3（ind < k - 1）， 执行结果如下：

ind < k - 1

③、当k = 1（inx > k - 1），执行结果如下：

inx > k - 1

观察该测试数据，可以发现在一轮排序的过程中，刚好将所有的数据排序完成了，此时难以验证快速选择算法的。所以我们更换一组测试数据，执行后观察：符合预期

        int[] arr = {8,2,3,5,10,7,19,4,14};

更换测试数据后