如何找出数组第k个最小的数？

数据结构与算法

1.暴力排序

排序之后直接选，。虽然肯定不能用这种方法，但是，。迫不得已，。，还是要用。。。

2.建堆

建一个节点数为k的小顶堆，堆顶就是要的结果

3.使用选择排序和冒泡排序思想

选择排序

首先知道选择排序的原理，假如我从前往后选择，那么第一个归位的数要么是第一大，要么是第一小。第二个归位的数要么是第二大，要么是第二小

时间复杂度为O（MN)

public class Solution {
    public int getKMin(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return 0;
        }
        //外循环是关键
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        System.out.println(nums[k - 1]);
        return nums[k - 1];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 0, 3, 5, 2, 1, 3, 4, 2, 4, 2};
        solution.getKMin(nums, 2);
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

冒泡排序
往数组尾下沉的话，第一趟下沉结束，末尾就是第一小或者第一大。第二趟下沉结束，末尾就是第二小或者第二大。。

public class Solution {
    public int getKMin(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return 0;
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] < nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        System.out.println(nums[nums.length - k]);
        return nums[nums.length - k];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 0, 3, 5, 2, 1, 3, 4, 2, 4, 2};
        solution.getKMin(nums, 1);
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

4.使用快排的思想（剪枝法）

假设归位一个数a,
那么a前面的数都比a小，a后面的数都比a大。而且后续的操作中a的位置都不会发生改变了。
假设a前面有count个数，那么这个a就是第count+1小。而且经过剪枝后的操作只会对某一个子序列进行。

public class Solution {
    public int getKMin(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1, k - 1);
        System.out.println("result:" + nums[k - 1]);
        return nums[k - 1];
    }
    public void quickSort(int[] nums, int left, int right, int k) {
        if (left > right) {
            return;
        }
        int temp = nums[left];
        int i = left;
        int j = right;
        while (i < j) {
        //找比他小的数，等于不要
            while (nums[j] >= temp && i < j) {
                j--;
            }
            while (nums[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                int temp1 = nums[i];
                nums[i] = nums[j];
                nums[j] = temp1;
            }
        }
        nums[left] = nums[i];
        nums[i] = temp;
        if (k < i) {
            quickSort(nums, left, i - 1, k);
        } else if (k > i) {
            quickSort(nums, i + 1, right, k);
        } else {
            return;
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 5, 3};
        solution.getKMin(nums, 3);
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}